503. 下一个更大元素 II#
503. 下一个更大元素 II - 力扣（Leetcode）
問題分析#
幾乎和「739. 每日溫度」一樣的一道題目，但卻改成了循環數組，所以在第一次遍歷完所有數組元素後，需要再從頭（下標 ）遍歷一次模擬循環。在第二次便利過程是為第一次遍歷未找到右側有更大值的元素查找目標值，所以不需要再在遍歷元素不大於棧元素時入棧的操作。
代碼實現#
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(), -1);
if (nums.size() == 1) return result;
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++) {
while (!st.empty() && nums[i] > nums[st.top()]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
return result;
}
};
42. 接雨水#
42. 接雨水 - 力扣（Leetcode）
一開始認為要以最大值為分界線，最大值左側遍歷時需要尋找當前遍歷元素往後的第一個更大的數，也就是說需要維護一個遞增單調棧；而最大值右側遍歷則與之相反。但寫完發現並不是如此，如 這個數據如果維護一個單調遞增棧，那麼如何計算雨水量。又想可以先維護單調遞減、再維護單調遞增，以此為一個區間不斷往後遍歷，但實現起來也不簡單。而且在我的兩種思路中都是通過累加每個柱子可以承接的雨水量（按列）來計算，增加了複雜性。
問題分析#
要計算凹槽的雨水量，需要知道中間柱子、左高柱子、右高柱子三個，然後通過長乘寬的思路來計算。
在維護單調棧的過程中當遍歷元素大於棧頂元素，此時就需要進行雨水量的計算。此時棧頂元素即為中間柱子，遍歷元素即為右高柱子，而左高柱子則剛好是棧彈出棧頂元素（中間柱子）後的棧頂元素。
當遍歷元素與棧頂元素相等時，彈出棧頂元素的操作是可選的，如果不彈出那麼會對相等柱子都進行計算，只不過棧中還有與之相等的柱子時雨水的高計算結果為 。
代碼實現#
class Solution {
public:
int trap(vector<int>& height) {
int result = 0;
if (height.size() <= 2) return result;
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[st.top()], height[i]) - height[mid];
int w = i - st.top() - 1;
result += h * w;
}
}
st.push(i);
}
}
return result;
}
};