503. 次の大きな要素 II#
503. 次の大きな要素 II - 力扣（Leetcode）
問題分析#
「739. 毎日の気温」とほぼ同じ問題ですが、循環配列に変更されているため、最初の一回の配列要素の走査が終わった後、再び先頭（インデックス 0）から走査する必要があります。2 回目の走査では、最初の走査で右側により大きな値が見つからなかった要素の目標値を探しますので、要素がスタックの要素よりも大きくない場合はスタックに入れる必要はありません。
コード実装#
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）
最初は最大値を境界として、最大値の左側の走査では、現在の走査要素の後ろの最初のより大きな数を探す必要があります。つまり、単調増加スタックを維持する必要があります。最大値の右側の走査はその逆です。しかし、書いてみるとそうではないことに気づきました。例えば、 このデータでは、単調増加スタックを維持すると、どのように雨の量を計算するかわかりません。最初に単調減少、次に単調増加を維持し、これを区間として後ろに進んでいく方法を考えましたが、実装は簡単ではありませんでした。また、私の 2 つのアイデアでは、列ごとに受けることができる雨の量を累積することで、複雑さが増してしまいます。
問題分析#
くぼみの雨の量を計算するには、中央の柱、左側の高い柱、右側の高い柱の 3 つを知る必要があります。そして、長さ × 幅の考え方を使って計算します。
単調スタックを維持する過程で、走査要素がスタックのトップ要素よりも大きい場合、雨の量を計算する必要があります。この場合、スタックのトップ要素（中央の柱）は、走査要素（右側の高い柱）は、左側の高い柱は、ちょうどスタックからポップした後のトップ要素です。
走査要素とスタックのトップ要素が等しい場合、スタックからポップする操作はオプションです。ポップしない場合、等しい柱に対して計算が行われ、ただし、スタックにはまだ等しい柱がある場合、雨の高さの計算結果は 0 になります。
コード実装#
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;
}
};