golang刷leetcode：使數(shù)組按非遞減順序排列

給你一個(gè)下標(biāo)從 0 開(kāi)始的整數(shù)數(shù)組 nums 。在一步操作中，移除所有滿(mǎn)足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。

重復(fù)執(zhí)行步驟，直到 nums 變?yōu)?非遞減 數(shù)組，返回所需執(zhí)行的操作數(shù)。

示例 1：

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

輸出：3

解釋?zhuān)簣?zhí)行下述幾個(gè)步驟：

- 步驟 1 ：[5,3,4,4,7,3,6,11,8,5,11] 變?yōu)?[5,4,4,7,6,11,11]

- 步驟 2 ：[5,4,4,7,6,11,11] 變?yōu)?[5,4,7,11,11]

- 步驟 3 ：[5,4,7,11,11] 變?yōu)?[5,7,11,11]

[5,7,11,11] 是一個(gè)非遞減數(shù)組，因此，返回 3 。

示例 2：

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

輸出：0

解釋?zhuān)簄ums 已經(jīng)是一個(gè)非遞減數(shù)組，因此，返回 0 。

提示：

1 <= nums.length <= 105

1 <= nums[i] <= 109

解題思路：

1，這種和附近元素相關(guān)的比較大小的算法一般是單調(diào)棧的思路。

2，題目思路分析，包括兩個(gè)場(chǎng)景：

A，后面的元素比它緊挨著的前一個(gè)元素小，需要?jiǎng)h除

B，如果幾個(gè)元素連續(xù)遞減可以被一次性刪除

C，同時(shí)出現(xiàn)多個(gè)符合條件A，B的元素可以一次刪除

3，對(duì)于位置i的元素，它一定被前面位置j的元素刪除，其中j<i,且nums[j]>nums[i]

4,其中符合條件3的元素被刪除的輪次為i，和之間刪除的元素的最大輪次+1

5，如果連續(xù)遞減，輪次不變

6，要求的就是最大輪次

7,如果棧中沒(méi)有元素說(shuō)明，當(dāng)前元素是第一個(gè)，或者是當(dāng)前最大的，它的輪次是0

8，如果沒(méi)有刪除情況下當(dāng)前元素比棧頂元素小，那么他們的輪次和棧頂元素是一樣的，是1

9，如果刪除過(guò)情況下，當(dāng)前元素比棧頂元素下，就是棧頂輪次加1，也就是3所說(shuō)的

代碼實(shí)現(xiàn)：

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 }

推薦閱讀

• golang刷leetcode：道路的最大總重要性