?

LeetCode 503 下一個(gè)更大元素II

題目鏈接：https://leetcode.cn/problems/next-greater-element-ii/

思路：

方法一:兩個(gè)for循環(huán)遍歷單調(diào)棧

第一個(gè)for循環(huán)確定數(shù)組中的某個(gè)值在右邊有最大的數(shù)，第二個(gè)for循環(huán)是為了可以使數(shù)組變成循環(huán)數(shù)組
例子：[5,4,3,2,1]
1、棧里 4,3,2,1,0](右邊為棧頂，棧內(nèi)元素為下標(biāo)）
2、從下標(biāo)0開始再次循環(huán)
(模擬一次就目標(biāo)了）

代碼：

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(); i++){if(nums[i] <= nums[st.top()])st.push(i);else{while(!st.empty() && nums[i] > nums[st.top()]){result[st.top()] = nums[i];st.pop();}st.push(i);}}for(int i = 0; i < nums.size(); i++){if(nums[i] <= nums[st.top()])st.push(i);else{while(!st.empty() && nums[i] > nums[st.top()]){result[st.top()] = nums[i];st.pop();}st.push(i);}}return result;}
};

方法二:單調(diào)棧，用取模的方法對數(shù)組進(jìn)行循環(huán)

代碼

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[i % nums.size()] > nums[st.top()]){result[st.top()] = nums[i % nums.size()];st.pop();}st.push(i % nums.size());}}return result;}
};

總結(jié)

關(guān)鍵在于如何循環(huán)數(shù)組

---

LeetCode 42 接雨水

題目鏈接：https://leetcode.cn/problems/trapping-rain-water/

思路：

本題關(guān)鍵點(diǎn)：

1. 接雨水重點(diǎn)在于要找當(dāng)前元素左邊第一個(gè)比它的元素和右邊第一個(gè)比它大的元素
2. 接雨水是按行來計(jì)算的
   
3. 明確h和w是如何計(jì)算的，w在計(jì)算中必須還要減1

代碼

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{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;}
};

總結(jié)

接雨水問題是經(jīng)典問題，后續(xù)要多加練習(xí)

---

今日總結(jié)：

還有一天，加油！