保存一个单调递减的stack,元素是(num, max+t)
遇到大于等于栈顶的,把栈顶的挪出来,然后记录同一次挪出的最大的max_t
如果挪完st还有剩余的话,max_t ++
然后ans就是取所有max_t的最大值
最后把(num, max_t)放到栈顶即可
class Solution:
def totalSteps(self, nums: List[int]) -> int:
ans = 0
st = [] # (num, max_t)
for num in nums:
max_t = 0
# 保持一个单调递减队列
while st and st[-1][0] <= num:
max_t = max(max_t, st.pop()[1])
# 若前面还能保留至少一个
if st: max_t += 1
ans = max(ans, max_t)
# 加入单调栈
st.append((num, max_t))
return ans
java code
class Solution {
public int totalSteps(int[] nums) {
var ans = 0;
// 用ArrayDeque模拟stack
var st = new ArrayDeque();
for(var num: nums) {
var max_t = 0;
while(!st.isEmpty() && st.peek()[0] <= num) {
max_t = Math.max(max_t, st.peek()[1]);
st.pop();
}
if(!st.isEmpty()) max_t++;
ans = Math.max(ans, max_t);
st.push(new int[]{num, max_t});
}
return ans;
}
}
总结
ArrayDeque里面放的是int[]
然后有isEmpty(), peek(), pop(), push()等封装好的栈的方法
学到了学到了



