算法训练营第五十九天|503.下一个更大元素II 42. 接雨水

本文主要是介绍算法训练营第五十九天|503.下一个更大元素II 42. 接雨水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode503.下一个更大元素II

文章链接：代码随想录
题目链接：503.下一个更大元素II

思路：相当于把两个数组拼在一起，用 % 操作节省时间复杂度

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);stack<int> st;st.push(0);for (int i = 1; i < nums.size() * 2; i++){if (nums[i % nums.size()] <= nums[st.top()]) st.push(i % nums.size());else {while (!st.empty() && nums[st.top()] < nums[i % nums.size()]){result[st.top()] = nums[i % nums.size()];st.pop();}st.push(i % nums.size());}}return result;}
};

精简版本

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);stack<int> st;st.push(0);for (int i = 1; i < nums.size() * 2; i++){//if (nums[i % nums.size()] <= nums[st.top()]) st.push(i % nums.size());// else{}while (!st.empty() && nums[st.top()] < nums[i % nums.size()]){result[st.top()] = nums[i % nums.size()];st.pop();}st.push(i % nums.size());}return result;}
};

Leetcode42. 接雨水

文章链接：[代码随想录](https://programmercarl.com/0042.%E6%8E%A5%E9%9B%A8%E6%B0%B4.html#%E6%80%9D%E8%B7%AF）
题目链接：42. 接雨水

思路：暴力双指针，时间超时，注意从左向右遍历时，右侧最大值的记录位置，不要将左边的最大值也记录上了

class Solution {
public:int trap(vector<int>& height) {int result = 0;int maxl = INT_MIN;int maxr;for(int i = 1; i < height.size() - 1; i++){for (int j = i - 1; j >= 0; j--){if (height[j] > maxl) maxl = height[j];}// 注意右侧最大值的记录位置，不要将左边的最大值也记录上了maxr = height[i + 1];for (int j = i + 2; j < height.size(); j++){if (height[j] > maxr) maxr = height[j];}int h = min(maxl, maxr)- height[i];cout << h << endl;if (h > 0) result += h;}return result;}
};

双指针优化，把每个位置左右两边的最大值提前记录，避免重复比较操作

class Solution {
public:int trap(vector<int>& height) {int result = 0;vector<int> maxl(height.size());vector<int> maxr(height.size());maxl[0] = height[0];maxr[height.size() - 1] = height[height.size() - 1];for (int i = 1; i < height.size(); i++){maxl[i] = max(height[i], maxl[i - 1]);}for (int i = height.size() - 2; i >= 0; i--){maxr[i] = max(height[i], maxr[i + 1]);}for (int i = 1; i < height.size() - 1; i++){int h = min(maxl[i - 1], maxr[i + 1]) - height[i];if (h > 0) result += h;}return result;}
};

双指针是按列求的，而单调栈是按行求的，不过感觉理解起来比前一种难一些

class Solution {
public:int trap(vector<int>& height) {int result = 0;stack<int> st;st.push(0);for (int i = 1; i < height.size(); i++){if (height[i] < height[st.top()]) st.push(i);else if (height[i] == height[st.top()]){st.pop();st.push(i);}else{while (!st.empty() && height[i] > height[st.top()]){int mid = st.top();st.pop();if (!st.empty()){int h = min(height[i], height[st.top()]) - height[mid];int w = i - st.top() - 1;result += h * w;}}st.push(i);}}return result;}
};