侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第五十九天 | 下一个更大元素II;接雨水

thinkTV
2023-06-17 / 0 评论 / 0 点赞 / 89 阅读 / 1,734 字 / 正在检测是否收录...

1. 下一个更大元素II

代码随想录:原文

力扣题目:503.下一个更大元素II

1. 思路

模拟循环数组的方法:

  1. 直接把两个数组拼接在一起,但扩充nums数组相当于多了一个O(n)

  2. 将数组取值×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

  • 如果按照列来计算的话,宽度一定是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 单调栈

  1. 首先单调栈是按照行方向来计算雨水:

图片-2

  1. 单调栈内元素的顺序:
    从栈头(元素从栈头弹出)到栈底的顺序应该是从小到大的顺序

  2. 遇到相同高度的柱子怎么办

    遇到相同的元素,更新栈内下标,就是将栈里元素(旧下标)弹出,将新元素(新下标)加入栈中
    因为我们要求宽度的时候 如果遇到相同高度的柱子,需要使用最右边的柱子来计算宽度

图片-9

  1. 栈里要保存什么数值
  • 栈里就存放下标就行,想要知道对应的高度,通过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;
    }
};
0

评论区