503. 下一个更大元素 II - 力扣（LeetCode）
思路
- 使用单调栈来找到下一个更大的元素,需要注意的就是因为是循环,所以得遍历两次,在i >= nums.size()时取下模即可
我的AC代码
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int> st;
vector<int> ans(nums.size(), -1);
for(int i = 0; i < 2 * nums.size(); ++i) {
int j = i % nums.size();
while(!st.empty() && nums[j] > nums[st.top()]) {
ans[st.top()] = nums[j];
st.pop();
}
st.push(j);
}
return ans;
}
};标准答案
// 时间复杂度O(n),空间复杂度O(n)
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;
}
};42. 接雨水 - 力扣（LeetCode）
思路
- 双指针法
- 双指针法按照列来计算雨水体积,如下图所示
- 雨水的面积是由接水的柱子左边最高的柱子和右边最高的柱子中更低的那个决定的,我们通过从左向右遍历和从右向左遍历找到每一个柱子左边最大的柱子和每一个柱子右边最大的柱子的高度,接下来再重新遍历一遍所有柱子,经过计算即可得出答案
- 单调栈法
- 单调栈法按照行来计算雨水体积,如下图所示
- 使用递减单调栈，分三种情况
-
- 栈顶元素和height[i]相等,弹出旧元素,让新元素入栈
- 栈顶元素大于height[i],直接入栈
- 栈顶元素小于height[i],构成凹槽,按照行来计算雨水量
我的AC代码
双指针法
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int trap(vector<int>& height) {
vector<int> lbig(height.size(), 0);
vector<int> rbig(height.size(), 0);
int ans = 0;
int max_num = 0;
for(int i = 0; i < height.size(); ++i) {
if(height[i] > max_num) {
max_num = height[i];
}
lbig[i] = max_num;
}
max_num = 0;
for(int i = height.size() - 1; i >= 0; --i) {
if(height[i] > max_num) {
max_num = height[i];
}
rbig[i] = max_num;
}
for(int i = 0; i < height.size(); ++i) {
if(lbig[i] != 0 && rbig[i] != 0) {
ans += min(lbig[i], rbig[i]) - height[i];
}
}
return ans;
}
};单调栈法
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
stack<int> st;
st.push(0);
for(int i = 1; i < height.size(); ++i) {
if(height[st.top()] == height[i]) {
st.pop();
st.push(i);
}
else if(height[st.top()] > height[i]) {
st.push(i);
}
else if(height[st.top()] < height[i]){
while(!st.empty() && height[i] > height[st.top()]) {
int mid = st.top();
int r = i;
st.pop();
if(!st.empty()) {
int l = st.top();
ans += (r - l - 1) * (min(height[r], height[l]) - height[mid]);
}
}
st.push(i);
}
}
return ans;
}
};标准答案
双指针法
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int trap(vector<int>& height) {
if (height.size() <= 2) return 0;
vector<int> maxLeft(height.size(), 0);
vector<int> maxRight(height.size(), 0);
int size = maxRight.size();
// 记录每个柱子左边柱子最大高度
maxLeft[0] = height[0];
for (int i = 1; i < size; i++) {
maxLeft[i] = max(height[i], maxLeft[i - 1]);
}
// 记录每个柱子右边柱子最大高度
maxRight[size - 1] = height[size - 1];
for (int i = size - 2; i >= 0; i--) {
maxRight[i] = max(height[i], maxRight[i + 1]);
}
// 求和
int sum = 0;
for (int i = 0; i < size; i++) {
int count = min(maxLeft[i], maxRight[i]) - height[i];
if (count > 0) sum += count;
}
return sum;
}
};单调栈法
// 时间复杂度O(n),空间复杂度O(n)
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;
}
};
Comments NOTHING