最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

有趣的算法题~单调栈

XAMPP案例 admin 586浏览 0评论

在刷 LeetCode 的时候,每次遇到精彩的题解都会感叹数据结构的伟大,通过巧妙地设计,能够非常清晰明了的解决问题。

什么是单调栈

单调栈分为单调递增栈和单调递减栈,单调递增栈即栈内元素保持单调递增的栈,同理单调递减栈即栈内元素保持单调递减的栈,跟单调队列差不多,但是只用到它的一端,利用它可以用来解决一些 ACM/ICPC 和 OI 的题目,如 RQNOJ 的诺的队列等【来源于百度百科的定义】

作用

可以以 O(1) 的时间复杂度得知某个位置左右两侧比他大(或小)的数的位置,当你需要高效率获取某个位置左右两侧比他大(或小)的数的位置的时候就可以用到单调栈。

做题

zzzzzs0071

思路

可以维护一个存储下标的单调栈,从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里,则表示尚未找到下一次温度更高的下标。正向遍历温度列表。

对于温度列表中的每个元素 T[i]

如果栈为空,则直接将 i 进栈,

如果栈不为空,则比较栈顶元素 prevIndex 对应的温度 T[prevIndex] 和当前温度 T[i]

如果 T[i] > T[prevIndex],则将 prevIndex 移除,并将 prevIndex对应的等待天数赋为 i - prevIndex

重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度,然后将 i 进栈。

 

为什么可以在弹栈的时候更新 resutl[prevIndex] 呢?

因为在这种情况下,即将进栈的 i 对应的 T[i] 一定是 T[prevIndex]右边第一个比它大的元素,试想如果 prevIndex 和 i 有比它大的元素,假设下标为 j,那么prevIndex 一定会在下标 j 的那一轮被弹掉。

 

由于单调栈满足从栈底到栈顶元素对应的温度递减,因此每次有元素进栈时,会将温度更低的元素全部移除,并更新出栈元素对应的等待天数,这样可以确保等待天数一定是最小的。

 

以下用一个具体的例子帮助读者理解单调栈。

对于温度列表 [73,74,75,71,69,72,76,73],单调栈 stack 的初始状态为空,结果result的初始状态是[0,0,0,0,0,0,0,0],按照以下步骤更新单调栈和答案,其中单调栈内的元素都是下标,括号内的数字表示下标在温度列表中对应的温度。

 

  • 当 i=0时,单调栈为空,因此将 0 进栈。
    • stack=[0(73)]
    • result=[0,0,0,0,0,0,0,0]
  • 当 i=1 时,由于 75 大于 74,因此移除栈顶元素 1,赋值 result[0]=1-0,将 1 进栈。
    • stack=[1(74)]
    • result=[1,0,0,0,0,0,0,0]
  • 当 i=2 时,由于 74 大于 73,因此移除栈顶元素 1,赋值 result[1]=2-1,将 1 进栈。
    • stack=[2(75)]
    • result=[1,1,0,0,0,0,0,0]
  • 当 i=3 时,由于 71 小于 75,因此将 3 进栈
    • stack=[2(75),3(71)]
    • result=[1,1,0,0,0,0,0,0]
  • 当 i=4 时,由于 69 小于 71,因此将 4 进栈
    • stack=[2(75),3(71),4(69)]
    • result=[1,1,0,0,0,0,0,0]
  • 当 i=5 时,由于 72 大于 69 和 71,因此依次移除栈顶元素 4 和 3,赋值 result[4]=5-4和 result[3]=5-3,将 5进栈。
    • stack=[2(75),3(72)]
    • result=[1,1,0,2,1,0,0,0]
  • 当 i=6 时,由于 76 大于 72 和 75,因此依次移除栈顶元素 5 和 2,赋值 result[5]=6-5和 result[2]=6-2,将 6进栈。
    • stack=[2(75),3(72)]
    • result=[1,1,0,2,1,0,0,0]
  • 当 i=7 时,由于 73 小于 76,因此将 7 进栈。
    • stack=[6(76),7(73)
    • result=[1,1,4,2,1,1,0,0]

Swift解题代码

func dailyTemperatures(_ T: [Int]) -> [Int] {
        var result = Array(repeating: 0, count: T.count)
        var stack = [Int]()
        for (index, value) in T.enumerated() {
            while !stack.isEmpty && T[stack.last!] < value {
                let preIndex = stack.popLast()!
                result[preIndex] = index - preIndex
            }
            stack.append(index)
        }

        return result
    }
end

转载请注明:XAMPP中文组官网 » 有趣的算法题~单调栈

您必须 登录 才能发表评论!