文章目录

• Day59_单调栈
• • 3. 下一个更大元素 II
  • 4. 接雨水

Day59_单调栈

3. 下一个更大元素 II

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

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

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

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

class Solution {
public:vector nextGreaterElements(vector& nums) {int nums_size = nums.size();vector result(nums_size, -1);stack 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;}
};

4. 接雨水

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

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

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

class Solution {
public:int trap(vector& 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;}
};

思路2：动态规划

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

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

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

class Solution {
public:int trap(vector& height) {int size = height.size();int sum = 0;vector left_h(size, 0);vector 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;}
};

思路3：单调栈

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

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

class Solution {
public:int trap(vector& height) {int size = height.size();int sum = 0;stack 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;}
};