使数组按非递减顺序排列 图解题解

这道题到底在问什么

输入

nums=[5,3,4,4,7,3,6,11,8,5,11]

输出

3

输入

nums=[4,5,7,7,13]

输出

0 (本来就非递减,不用删)

最优解：一步一步想明白

1. 3记牢这一句:每一轮基于本轮开始的数组同时删,谁的左邻比自己大谁就被删。下面从第一轮开始,一对一对地扫。
2. 4准备逐轮删除这是初始数组 5,3,4,4,7,3,6。从左往右看,3 比前面的 5 小,是个下降;7 后面又掉到 3,也是下降。只要还存在这种下降,数组就不是非递减,就得继续删。灰色代表已删除(现在一个都没有),红色代表本轮待删,现在开始第一轮。
3. 5第 1 轮 · 扫描相邻对第 1 轮开始。当前还活着的是 5, 3, 4, 4, 7, 3, 6 这 7 个数(灰色的是前几轮已经删掉的,固定留在原位当占位)。我拿这一轮开始时的这串数,从左往右一对一对地看,谁的左邻比自己大,就把谁标红等着删。
4. 6第 1 轮 · 第 1 对看这一对:左边绿色的基准要么是保留的邻居、要么已经标红,右边紫色是 3。左邻的值 5 比 3 大,构成下降,所以 3 这一步要被删,把它标红。注意它标红后并不马上消失,还要继续给它右边的数当比较基准。
5. 7第 1 轮 · 第 2 对看这一对:左边是 3,右边紫色是 4。3 没有比 4 大,这里不是下降,4 本轮保留,不标红。继续看下一对。
6. 8第 1 轮 · 第 3 对看这一对:左边是 4,右边紫色是 4。4 没有比 4 大,这里不是下降,4 本轮保留,不标红。继续看下一对。
7. 9第 1 轮 · 第 4 对看这一对:左边是 4,右边紫色是 7。4 没有比 7 大,这里不是下降,7 本轮保留,不标红。继续看下一对。
8. 10第 1 轮 · 第 5 对看这一对:左边绿色的基准要么是保留的邻居、要么已经标红,右边紫色是 3。左邻的值 7 比 3 大,构成下降,所以 3 这一步要被删,把它标红。注意它标红后并不马上消失,还要继续给它右边的数当比较基准。
9. 11第 1 轮 · 第 6 对看这一对:左边是 3,右边紫色是 6。3 没有比 6 大,这里不是下降,6 本轮保留,不标红。继续看下一对。
10. 12第 1 轮完成第 1 轮结算:刚才标红的 3, 3 这 2 个数同时被删,一起灰掉。剩下绿色的 5, 4, 4, 7, 6 是本轮的幸存者。已完成 1 轮。再看看它还降不降,降就接着来下一轮。
11. 13第 2 轮 · 扫描相邻对第 2 轮开始。当前还活着的是 5, 4, 4, 7, 6 这 5 个数(灰色的是前几轮已经删掉的,固定留在原位当占位)。我拿这一轮开始时的这串数,从左往右一对一对地看,谁的左邻比自己大,就把谁标红等着删。
12. 14第 2 轮 · 第 1 对看这一对:左边绿色的基准要么是保留的邻居、要么已经标红,右边紫色是 4。左邻的值 5 比 4 大,构成下降,所以 4 这一步要被删,把它标红。注意它标红后并不马上消失,还要继续给它右边的数当比较基准。
13. 15第 2 轮 · 第 2 对看这一对:左边是 4,右边紫色是 4。4 没有比 4 大,这里不是下降,4 本轮保留,不标红。继续看下一对。
14. 16第 2 轮 · 第 3 对看这一对:左边是 4,右边紫色是 7。4 没有比 7 大,这里不是下降,7 本轮保留,不标红。继续看下一对。
15. 17第 2 轮 · 第 4 对看这一对:左边绿色的基准要么是保留的邻居、要么已经标红,右边紫色是 6。左邻的值 7 比 6 大,构成下降,所以 6 这一步要被删,把它标红。注意它标红后并不马上消失,还要继续给它右边的数当比较基准。
16. 18第 2 轮完成第 2 轮结算:刚才标红的 4, 6 这 2 个数同时被删,一起灰掉。剩下绿色的 5, 4, 7 是本轮的幸存者。已完成 2 轮。再看看它还降不降,降就接着来下一轮。
17. 19第 3 轮 · 扫描相邻对第 3 轮开始。当前还活着的是 5, 4, 7 这 3 个数(灰色的是前几轮已经删掉的,固定留在原位当占位)。我拿这一轮开始时的这串数,从左往右一对一对地看,谁的左邻比自己大,就把谁标红等着删。
18. 20第 3 轮 · 第 1 对看这一对:左边绿色的基准要么是保留的邻居、要么已经标红,右边紫色是 4。左邻的值 5 比 4 大,构成下降,所以 4 这一步要被删,把它标红。注意它标红后并不马上消失,还要继续给它右边的数当比较基准。
19. 21第 3 轮 · 第 2 对看这一对:左边是 4,右边紫色是 7。4 没有比 7 大,这里不是下降,7 本轮保留,不标红。继续看下一对。
20. 22第 3 轮完成第 3 轮结算:刚才标红的 4 这 1 个数同时被删,一起灰掉。剩下绿色的 5, 7 是本轮的幸存者。已完成 3 轮。再看看它还降不降,降就接着来下一轮。
21. 23第 4 轮 · 扫描相邻对第 4 轮开始。当前还活着的是 5, 7 这 2 个数(灰色的是前几轮已经删掉的,固定留在原位当占位)。我拿这一轮开始时的这串数,从左往右一对一对地看,谁的左邻比自己大,就把谁标红等着删。
22. 24第 4 轮 · 第 1 对看这一对:左边是 5,右边紫色是 7。5 没有比 7 大,这里不是下降,7 本轮保留,不标红。继续看下一对。
23. 25结束 · 答案 = 3这一轮从头扫到尾,没有任何一对是左大右小,一个红都没标出来。说明剩下的 5, 7 已经是非递减了,操作到此为止。回头数一数,真正发生删除的一共是 3 轮,所以答案就是 3。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        stk = []
        ans, n = 0, len(nums)
        dp = [0] * n
        for i in range(n - 1, -1, -1):
            while stk and nums[i] > nums[stk[-1]]:
                dp[i] = max(dp[i] + 1, dp[stk.pop()])
            stk.append(i)
        return max(dp)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int totalSteps(vector<int>& nums) {
        stack<int> stk;
        int ans = 0, n = nums.size();
        vector<int> dp(n);
        for (int i = n - 1; i >= 0; --i) {
            while (!stk.empty() && nums[i] > nums[stk.top()]) {
                dp[i] = max(dp[i] + 1, dp[stk.top()]);
                ans = max(ans, dp[i]);
                stk.pop();
            }
            stk.push(i);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int totalSteps(int[] nums) {
        Deque<Integer> stk = new ArrayDeque<>();
        int ans = 0;
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            while (!stk.isEmpty() && nums[i] > nums[stk.peek()]) {
                dp[i] = Math.max(dp[i] + 1, dp[stk.pop()]);
                ans = Math.max(ans, dp[i]);
            }
            stk.push(i);
        }
        return ans;
    }
}

复杂度

面试官可能追问