算法leetcode

力扣962-最大宽度坡

字数统计: 555字   |   阅读时长: 2分
,

摘要: 本文是力扣 962 的题解，单调栈的基础应用。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们看一个单调栈的问题，力扣 962。本题解决之后，可以作为组件，直接解决力扣 1124。

$1 题目

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

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

1
2
3
提示：
2 <= A.length <= 50000
0 <= A[i] <= 50000

示例 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.

$2 题解

算法: 单调栈

因为对起点i, 考虑 i 右侧的 $j1 < j2$, 若 $sums[j1] < sums[j2]$, 则j1无用,因为对任意i, 若j1为候选,则j2总会更好,因此可能的右端点为从右到左单调递增的子序列. 同理可能的左端点是从左到右的单调递减的子序列.

先预处理出两个单调栈的元素: 可能的 i 下标和可能的 j 下标, 然后从右往左枚举 veci, 操作 vecj.

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        if(A.empty()) return 0;
        int n = A.size();
        vector<int> veci, vecj;
        veci.push_back(0);
        int cur = A[0];
        for(int i = 1; i < n; ++i)
        {
            if(A[i] < cur)
            {
                veci.push_back(i);
                cur = A[i];
            }
        }
        vecj.push_back(n - 1);
        cur = A[n - 1];
        for(int j = n - 2; j >= 0; --j)
        {
            if(A[j] > cur)
            {
                vecj.push_back(j);
                cur = A[j];
            }
        }
        int ni = veci.size(), nj = vecj.size();
        int j = 0;
        int result = 0;
        for(int i = ni - 1; i >= 0; --i)
        {
            while(j < nj && A[vecj[j]] < A[veci[i]])
                ++j;
            if(j < nj)
                result = max(result, vecj[j] - veci[i]);
        }
        return result;
    }
};
Share