这道题在赛时尝试了很多局部正确的做法，也就是贪心。现在想来这种题目大概就是一步步把每个细节都思考清楚，再通过不断尝试才可能通过的题？以上仅个人愚见。
题意：
给你一个下标从
0
0
0 开始的整数数组
n
u
m
s
nums
nums 。在一步操作中，移除所有满足
n
u
m
s
[
i
−
1
]
>
n
u
m
s
[
i
]
nums[i - 1] > nums[i]
nums[i−1]>nums[i] 的
n
u
m
s
[
i
]
nums[i]
nums[i] ，其中
0
<
i
<
n
u
m
s
.
l
e
n
g
t
h
0 < i < nums.length
0
1
≤
n
u
m
s
.
l
e
n
g
t
h
≤
1
0
5
1 leq nums.length leq 10^5
1≤nums.length≤105
1
≤
n
u
m
s
[
i
]
≤
1
0
9
1 leq nums[i] leq 10^9
1≤nums[i]≤109
题解：
直观想法：
考虑每个元素被删除的时间点，元素 n u m s [ i ] nums[i] nums[i] 如果可以被删除，一定是被它左边第一个比它大的元素 n u m s [ j ] , j < i nums[j],j
d
p
[
i
]
dp[i]
dp[i] 表示将前
i
i
i 个元素按照题目所示变成非递减数组的最迟时间点。
初始
d
p
[
i
]
=
0
dp[i]=0
dp[i]=0
当存在
n
u
m
s
[
i
]
<
n
u
m
s
[
i
−
1
]
nums[i]
所以，
n
u
m
s
[
i
]
nums[i]
nums[i] 被删除的时间点等于
n
u
m
s
[
i
+
1
,
.
.
.
,
j
−
1
]
nums[i + 1,...,j - 1]
nums[i+1,...,j−1] 这些元素中最大被删除的时间点 + 1
一种显然的策略是： t [ i ] t[i] t[i] 表示第 i i i 个数被删除的时间点，类似 d p dp dp 的思想， O ( n 2 ) O(n^2) O(n2) 转移
class Solution {
public:
int totalSteps(vector& nums) {
// t[i] 表示将第 i 个数 按照题目要求维护成一个非递减数组，需要的操作次数
int n = nums.size();
vector t(n, 0);
int maxv = nums[0];
for(int i = 1; i < n; ++i) {
int temp = 0;
for(int j = i - 1; j >= 0; --j) {
if(nums[j] > nums[i]) break;
temp = max(temp, t[j]);
}
if(nums[i] < maxv) t[i] = temp + 1;
maxv = max(maxv, nums[i]);
}
int ans = 0;
for(int i = 0; i < n; ++i)
ans = max(ans, t[i]);
return ans;
}
};
显然时间复杂度是不够优秀的，再来思考如何优化第二层循环。
因为
n
u
m
s
[
i
]
nums[i]
nums[i] 一定不小于
n
u
m
s
[
j
+
1
,
.
.
.
,
i
−
1
]
nums[j+1,...,i-1]
nums[j+1,...,i−1]，而
t
[
i
]
t[i]
t[i] 也一定比
t
[
j
+
1
,
.
.
.
,
i
−
1
]
t[j+1,...,i-1]
t[j+1,...,i−1]大。
这样一个显然的策略是，维护一个单调递减的栈，栈中单调递减的为元素的值
n
u
m
s
[
i
]
nums[i]
nums[i] ，同时存储这个元素被删除的时间点
t
[
i
]
t[i]
t[i] 。
这里使用单调递减的栈的原因是，之后的元素
n
u
m
s
[
k
]
,
k
>
i
(
n
u
m
s
[
k
]
>
n
u
m
s
[
i
]
)
nums[k], k>i(nums[k]>nums[i])
nums[k],k>i(nums[k]>nums[i])， 并不由
n
u
m
s
[
i
]
nums[i]
nums[i] 删除，而是由在栈中的大于
n
u
m
s
[
i
]
nums[i]
nums[i] 的元素
n
u
m
s
[
j
]
(
j
<
i
,
n
u
m
s
[
j
]
>
n
u
m
s
[
i
]
,
n
u
m
s
[
j
]
>
n
u
m
s
[
k
]
)
nums[j](j
代码：
class Solution {
public:
int totalSteps(vector& nums) {
int n = nums.size();
stack> stk;
int ans = 0;
for(int i = 0; i < n; ++i) {
int t = 0;
while(!stk.empty() && stk.top().first <= nums[i]) {
t = max(t, stk.top().second);
stk.pop();
}
if(stk.empty()) t = 0; // 0~i-1中没有元素大于nums[i]
else t += 1;
stk.push({nums[i], t});
ans = max(ans, t);
}
return ans;
}
};
