随想录一刷Day59——单调栈

Day59_单调栈

3. 下一个更大元素 II

503. 下一个更大元素 II
思路：

方法一：
将数组复制一份拼接在尾部，然后对整个新数组利用单调栈求结果，最后将结果resize成原数组的大小

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int nums_size = nums.size();
        nums.insert(nums.end(), nums.begin(), nums.end()); // 两个数组拼接在一起
        nums_size *= 2;
        vector<int> result(nums_size, -1);

        stack<int> stk;
        stk.push(0);
        for (int i = 1; i < nums_size; i++) {
            while (!stk.empty() && nums[i] > nums[stk.top()]) {
                result[stk.top()] = nums[i];
                stk.pop();
            }
            stk.push(i);
        }
        result.resize(nums_size / 2);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二：
优化一下，把插入元素和resize操作去掉，模拟数组复制两份的情况

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int nums_size = nums.size();
        vector<int> result(nums_size, -1);

        stack<int> stk;
        stk.push(0);
        for (int j = 1; j < nums_size * 2; j++) {
            int i = j % nums_size;
            while (!stk.empty() && nums[i] > nums[stk.top()]) {
                result[stk.top()] = nums[i];
                stk.pop();
            }
            stk.push(i);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4. 接雨水

42. 接雨水
思路1：双指针

遍历整个数组，找到每个柱子左右最高的柱子来判断该列可以接到多少水，累计所有柱子可以接到的水量。（首尾柱子不接水）

超时了（＞人＜；）
时间复杂度： $O(n^2)$
空间复杂度： $O(1)$

class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();
        int sum = 0;
        for (int i = 1; i < size - 1; i++) {
            int left_height = height[i];
            int right_height = height[i];
            for (int j = i - 1; j >= 0; j--) left_height = max(left_height, height[j]);
            for (int j = i + 1; j < size; j++) right_height = max(right_height, height[j]);
            sum += min(left_height, right_height) - height[i];
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

思路2：动态规划

双指针多次重复计算去找每一列的左右边界，使用数组将左右边界的值记录下来，可以省去重复的查找，这里用到了动态规划的思想，递推公式如下：

• 左边界： leftheight[i] = max(leftheight[i], leftheight[i - 1]);
• 右边界：rightheight[i] = max(rightheight[i], rightheight[i - 1];

时间复杂度： $O(n)$
空间复杂度： $O(n)$

class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();
        int sum = 0;
        vector<int> left_h(size, 0);
        vector<int> right_h(size, 0);

        left_h[0] = height[0];
        for (int i = 1; i < size; i++) left_h[i] = max(left_h[i - 1], height[i]);
        right_h[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) right_h[i] = max(right_h[i + 1], height[i]);

        for (int i = 1; i < size - 1; i++) sum += max(0, min(left_h[i], right_h[i]) - height[i]);
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路3：单调栈

按行计算
计算获取单调栈，每次出现比栈顶元素大的元素时，说明出现了凹槽，该凹槽内的储水量是，高度是左右边界最小值与栈顶元素的差，宽度是右边界-左边界-1

时间复杂度： $O(n)$
空间复杂度： $O(n)$

class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();
        int sum = 0;
        stack<int> stk;
        stk.push(0);
        for (int i = 1; i < size; i++) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int mid = height[stk.top()];
                stk.pop();
                if (!stk.empty()) { // 有左右边界则可以储水
                    int h = min(height[i], height[stk.top()]) - mid;
                    int w = i - stk.top() - 1;
                    sum += h * w;
                } // 只有单个边界不能存水
            }
            stk.push(i);
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22