golang刷leetcode：使数组按非递减顺序排列

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。

重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。

示例 1：

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

输出：3

解释：执行下述几个步骤：

- 步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11]

- 步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11]

- 步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11]

[5,7,11,11] 是一个非递减数组，因此，返回 3 。

示例 2：

输入：nums = [4,5,7,7,13]

输出：0

解释：nums 已经是一个非递减数组，因此，返回 0 。

提示：

1 <= nums.length <= 105

1 <= nums[i] <= 109

解题思路：

1，这种和附近元素相关的比较大小的算法一般是单调栈的思路。

2，题目思路分析，包括两个场景：

A，后面的元素比它紧挨着的前一个元素小，需要删除

B，如果几个元素连续递减可以被一次性删除

C，同时出现多个符合条件A，B的元素可以一次删除

3，对于位置i的元素，它一定被前面位置j的元素删除，其中j<i,且nums[j]>nums[i]

4,其中符合条件3的元素被删除的轮次为i，和之间删除的元素的最大轮次+1

5，如果连续递减，轮次不变

6，要求的就是最大轮次

7,如果栈中没有元素说明，当前元素是第一个，或者是当前最大的，它的轮次是0

8，如果没有删除情况下当前元素比栈顶元素小，那么他们的轮次和栈顶元素是一样的，是1

9，如果删除过情况下，当前元素比栈顶元素下，就是栈顶轮次加1，也就是3所说的

代码实现：

func totalSteps(nums []int) (ans int) {
  var stack []numOrder
    for _,num:=range nums{
        maxOrder:=0
        for len(stack)>0 && stack[len(stack)-1].num<=num{
            maxOrder=max(maxOrder,stack[len(stack)-1].order)
            stack=stack[:len(stack)-1]
        }
        if len(stack)>0{
            maxOrder++
        }
        ans=max(ans,maxOrder)
        stack=append(stack,numOrder{
            num:num,
            order:maxOrder,
        })
    }
    return
}

type numOrder struct{ num, order int }

func max(a, b int) int { if b > a { return b }; return a }

复制