2289. 使数组按非递减顺序排列

给你一个下标从 开始的整数数组 。在一步操作中,移除所有满足  ,其中

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

示例 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

提示

解法一

首先知道了这题是单调栈,然后直接往这个方向上想,糊了一个很奇怪的解法,但是 AC 了,看了题解区没有和我一样的。

我的理解是,逆序构建一个单调递减栈,栈中的元素都是待消除的,栈中相邻的元素必然不是同一轮被消除,所以统计最大的消除深度就是最大的轮次,时间复杂度

// [5,3,4,4,7,3,6,11,8,5,11]
// [7,14,4,14,13,2,6,13] --> [7,14,14,6,13]
func totalSteps(nums []int) int {
var stack []int
var res = 0
var maxDepth = 0
for i := len(nums) - 1; i >= 0; i-- {
for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
stack = stack[:len(stack)-1]
res = Max(res, maxDepth-len(stack))
}
stack = append(stack, i)
maxDepth = Max(maxDepth, len(stack))
}
return res
}

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

解法二

如果是比赛的时候肯定是没时间去想单调栈的解法,链表模拟是比较自然的想法。

模拟的能力比较差,思路不清晰,还需要多练一下。

func totalSteps(nums []int) int {
nums = append(nums, 0x3f3f3f3f)
next := make([]int, len(nums))
var lis []int
for i := 0; i < len(nums)-1; i++ {
next[i] = i + 1
}

// 存放可以吞噬其它数的数,注意逆序存
// 3->2->1 逆序才能一次删除 2 和 1
for i := len(nums) - 2; i >= 0; i-- {
if nums[i] > nums[i+1] {
lis = append(lis, i)
}
}

for op := 0; ; op++ {
var temp []int
for _, i := range lis {
if nums[i] > nums[next[i]] {
// 吞噬后面的数
next[i] = next[next[i]]
// 还可能继续吞
temp = append(temp, i)
}
}
// 没有能吞的了
if len(temp) == 0 {
return op
}
lis = temp
}
return -1
}

2290. 到达角落需要移除障碍物的最小数目

给你一个下标从 开始的二维整数数组 ,数组大小为 。每个单元格都是两个值之一:

表示一个 空 单元格,
表示一个可以移除的 障碍物 。

你可以向上、下、左、右移动,从一个空单元格移动到另一个空单元格。

现在你需要从左上角  移动到右下角 ,返回需要移除的障碍物的最小数目。

示例 1

输入:grid = [[0,1,1],[1,1,0],[1,1,0]]
输出:2
解释:可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。
可以证明我们至少需要移除两个障碍物,所以返回 2
注意,可能存在其他方式来移除 2 个障碍物,创建出可行的路径。

示例 2

输入:grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
输出:0
解释:不移除任何障碍物就能从 (0, 0) 到 (2, 4) ,所以返回 0

 
提示

解法一

0-1BFS,很直白,比 t3 简单,时间复杂度

func minimumObstacles(grid [][]int) int {

INF := 0x3f3f3f3f
dir := []int{1, 0, -1, 0, 1}
M, N := len(grid), len(grid[0])
que := list.New()
que.PushBack([]int{0, 0})

vis := make([][]bool, M)
dis := make([][]int, M)
for i := 0; i < M; i++ {
vis[i] = make([]bool, N)
dis[i] = make([]int, N)
for j := 0; j < N; j++ {
dis[i][j] = INF
}
}

dis[0][0] = 0
for que.Len() > 0 {
t := que.Front().Value.([]int)
que.Remove(que.Front())
x, y := t[0], t[1]
if x == M-1 && y == N-1 {
break
}
if vis[x][y] {
continue
}
vis[x][y] = true
for i := 0; i < len(dir)-1; i++ {
nx, ny := x+dir[i], y+dir[i+1]
if nx < 0 || ny < 0 || nx >= M || ny >= N {
continue
}

if dis[nx][ny] > dis[x][y]+grid[nx][ny] {
dis[nx][ny] = dis[x][y] + grid[nx][ny]
if grid[nx][ny] == 1 {
que.PushBack([]int{nx, ny})
} else {
que.PushFront([]int{nx, ny})
}
}
}
}
return dis[M-1][N-1]
}