力扣 295th 周赛

2022-06-01 约 1212 字预计阅读 3 分钟

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

给你一个下标从 $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 <= 10^5$
$1 <= nums[i] <= 10^9$

解法一

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

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

// [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. 到达角落需要移除障碍物的最小数目

给你一个下标从 $0$ 开始的二维整数数组 $grid$ ，数组大小为 $m \ast n$ 。每个单元格都是两个值之一：

$0$ 表示一个空单元格， $1$ 表示一个可以移除的障碍物。

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

现在你需要从左上角 $(0, 0)$ 移动到右下角 $(m - 1, n - 1)$ ，返回需要移除的障碍物的最小数目。

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

提示：

$m = grid.length$
$n = grid[i].length$
$1 <= m, n <= 10^5$
$2 <= m \ast n <= 10^5$
$grid[i][j]$ 为 $0$ 或 $1$
$grid[0][0] = grid[m - 1][n - 1] = 0$

解法一

0-1BFS，很直白，比 t3 简单，时间复杂度 $O(M \ast N)$

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]
}

目录

力扣 295th 周赛

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

解法一

解法二

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

解法一