esc to dismiss

962. 最大宽度坡

题目

给定一个整数数组 A,坡是元组 (i, j),其中  i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。

找出 A 中的坡的最大宽度,如果不存在,返回 0 。

示例 1:

输入:[6,0,8,2,1,5]

输出:4

解释:

最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.

示例 2:

输入:[9,8,1,0,1,9,4,0,4,1]

输出:7

解释:

最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1

解体思路

开始时我当成滑动窗口来做,但是逻辑搞的很复杂,而且有很多场景都没考虑全面,因为用例失败很多次后,终于写了个很复杂的代码提交成功了,但运行效率也比较低。

官方的题解是 排序 和 二分检索候选位置,但看上去也挺复杂。

《九阴真经》中说该题用 单调栈 ,理解起来容易得多,而且很巧妙。最终提交代码如下:

func maxWidthRamp(A []int) int {
    var mono []int
    max := 0

    for i, v := range A {
        if len(mono) == 0 || A[mono[len(mono)-1]] > v {
            mono = append(mono, i)
        }

        if v == 0 {
            break
        }
    }

    for i := len(A) - 1; i >= 0; i-- {
        for len(mono) > 0 && A[mono[len(mono)-1]] <= A[i] {
            ramp := i - mono[len(mono)-1]
            if ramp > max {
                max = ramp
            }
            mono = mono[:len(mono)-1]
        }

        if len(mono) == 0 {
            break
        }
    }

    return max
}

这道题不能简单的套用单调栈,而需要一定的变化。

首先从左到右,向单调栈内插入元素,由于不需要记录状态,因此,只需判断待入栈数据是否小于栈顶元素,如果小于则入栈,否则不管。因为题目中的最小数是0,因此如果碰到0,即停止。

然后从右到左取数组的右值,从单调栈顶开始比较,如果右值大于等于栈顶元素,则记录该差值,并退出栈顶元素。该差值中最大的即为答案。等单调栈全部退栈或遍历到最左结束比较。

解题的思路其实就是:如果 (i, j) 是最大宽度坡的话,那么 i 一定是满足条件的最左,而 j 一定是满足条件的最右。总之,这是个很巧妙的利用单调栈解题的方法。

经验教训

本题我当成滑窗来做了,正确的解法应该是 单调栈

还是那句话,用错算法会很惨,如何选择最合适的算法是个值得探索的话题。

x