1. 下一个更大元素II
代码随想录：原文
力扣题目：503.下一个更大元素II
1. 思路
模拟循环数组的方法：
-
直接把两个数组拼接在一起，但扩充nums数组相当于多了一个O(n)
-
将数组取值×2，
for (int i = 1; i < nums.size() * 2; i++)，再遍历时对i取模来模拟循环数组：nums[i % nums.size()]
使用方法二的思路，结合下一个更大元素Ⅰ即可。
1.2 代码实现
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 0) return result;
stack<int> st;
for (int i = 0; i < nums.size() * 2; i++) {
// 模拟遍历两边nums，注意一下都是用i % nums.size()来操作
while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
result[st.top()] = nums[i % nums.size()];
st.pop();
}
st.push(i % nums.size());
}
return result;
}
};
2. 接雨水
代码随想录：原文
力扣题目：42. 接雨水
2.1 思路
2.1.1 暴力解法
- 本题暴力解法也是也是使用双指针。
- 首先要明确，要按照行来计算，还是按照列（推荐）来计算
- 如果按照列来计算的话，宽度一定是1了，我们再把每一列的雨水的高度求出来就可以了
- 首先从头遍历所有的列，并且要注意第一个柱子和最后一个柱子不接雨水
for (int i = 0; i < height.size(); i++) {
// 第一个柱子和最后一个柱子不接雨水
if (i == 0 || i == height.size() - 1) continue;
}
在for循环中求左右两边最高柱子，代码如下：
int rHeight = height[i]; // 记录右边柱子的最高高度
int lHeight = height[i]; // 记录左边柱子的最高高度
for (int r = i + 1; r < height.size(); r++) {
if (height[r] > rHeight) rHeight = height[r];
}
for (int l = i - 1; l >= 0; l--) {
if (height[l] > lHeight) lHeight = height[l];
}
最后，计算该列的雨水高度，代码如下：
int h = min(lHeight, rHeight) - height[i];
if (h > 0) sum += h; // 注意只有h大于零的时候，在统计到总和中
2.1.2 双指针优化
- 暴力算法中，当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度
- 为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的
- 我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算
左边的最高高度是前一个位置的左边最高高度和本高度的最大值
从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1])
从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1])
2.1.3 单调栈
- 首先单调栈是按照行方向来计算雨水：
-
单调栈内元素的顺序：
从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序 -
遇到相同高度的柱子怎么办
遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中
因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度
- 栈里要保存什么数值
- 栈里就存放下标就行，想要知道对应的高度，通过height[stack.top()] 就知道弹出的下标对应的高度了
stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度
单调栈处理逻辑
-
情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]
- 遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中
-
情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]
- 如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度
-
情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]
- 如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了
- 取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]
- 此时的栈顶元素st.top()，就是凹槽的左边位置，下标为st.top()，对应的高度为height[st.top()]
- 当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]
- 求当前凹槽雨水的体积代码如下：
while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while，持续跟新栈顶元素
int mid = st.top();
st.pop();
if (!st.empty()) {
int h = min(height[st.top()], height[i]) - height[mid];
int w = i - st.top() - 1; // 注意减一，只求中间宽度
sum += h * w;
}
}
2.2 代码实现
2.2.1 暴力方法
class Solution {
public:
int trap(vector<int>& height) {
int sum = 0;
for (int i = 0; i < height.size(); i++) {
// 第一个柱子和最后一个柱子不接雨水
if (i == 0 || i == height.size() - 1) continue;
int rHeight = height[i]; // 记录右边柱子的最高高度
int lHeight = height[i]; // 记录左边柱子的最高高度
for (int r = i + 1; r < height.size(); r++) {
if (height[r] > rHeight) rHeight = height[r];
}
for (int l = i - 1; l >= 0; l--) {
if (height[l] > lHeight) lHeight = height[l];
}
int h = min(lHeight, rHeight) - height[i];
if (h > 0) sum += h;
}
return sum;
}
};
2.2.2 单调栈
class Solution {
public:
int trap(vector<int>& height) {
if (height.size() <= 2) return 0; // 可以不加
stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度
st.push(0);
int sum = 0;
for (int i = 1; i < height.size(); i++) {
if (height[i] < height[st.top()]) { // 情况一
st.push(i);
} if (height[i] == height[st.top()]) { // 情况二
st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。
st.push(i);
} else { // 情况三
while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while
int mid = st.top();
st.pop();
if (!st.empty()) {
int h = min(height[st.top()], height[i]) - height[mid];
int w = i - st.top() - 1; // 注意减一，只求中间宽度
sum += h * w;
}
}
st.push(i);
}
}
return sum;
}
};
评论区