一、3417. 跳过交替单元格的之字形遍历

题目链接

本题是一道模拟题，第一行走0，2，4，…偶数下标的格子，第二行走1，3，5，…奇数下标的格子（要倒着遍历），可以发现规律：

• 偶数行从前往后遍历偶数下标的格子
• 奇数行从后往前遍历奇数下标的格子

代码如下：

class Solution {
    public List<Integer> zigzagTraversal(int[][] g) {
        List<Integer> ans = new ArrayList<>();
        boolean flg = false;
        int n = g.length, m = g[0].length;
        for(int i=0; i<g.length; i++){
            if(!flg){
                for(int j=0; j<m; j+=2){
                    ans.add(g[i][j]);
                }
            }else{
                for(int j=m-1-m%2; j>=0; j-=2){
                    ans.add(g[i][j]);
                }
            }
            flg = !flg;
        }
        return ans;
    }
}

二、3418. 机器人可以获得的最大金币数

题目链接

定义 $f[i][j][k]$ : 从 $(0,0)$ 到 $(i,j)$ 且感化最多 $k$ 个强盗可获得的最大金币数量。
选或不选 $x=coins[i][j]$：

• 不选 $x$，它只能从 $(i-1,j)$ 和 $(i,j-1)$ 转移过来，此时它的 $k$ 也不会发生变化，即 $f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k])$
• 选择 $x$，它只能从 $(i-1,j)$ 和 $(i,j-1)$ 转移过来，此时它的 $k$ 需要分情况讨论：
  • $if(k>0$ && $x<0)$，此时可以感化当前单元格的强盗，即当前不获得也不损失金币，即 $f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1],f[i][j-1][k-1])$
  • 不使用感化能力次数 $k$，直接选 $x$，即$f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]+x,f[i][j-1][k-1]+x)$

PS：

• 这里$f[i][j]$是从$f[i-1][j]$和$f[i][j-1]$转移过来的，还需要注意越界访问，并且需要预处理第一行和第一列的值，所以在开数组的时候可以多开一行一列，此时递推公式就变成了 $f[i+1][j+1]=max(f[i+1][j],f[i][j+1])$。就不需要使用 $if$ 判断是否越界了
• 该题的答案可以为负值，所以需要在初始化的时候将所有位置置为$-inf$，除了 $f[0][1][k]$ 和 $f[1][0][k]$ $(k\in [0,2])$，因为$f[1][1][k]$ 即 $(0,0)$需要从上述两个状态转移过来，如果置为$-inf$，它在$(0,0)$位置的值就变成了$-inf$，这显然不符合题意。

代码如下：

class Solution {
    public int maximumAmount(int[][] coins) {
        int n = coins.length, m = coins[0].length;
        int[][][] f = new int[n+1][m+1][3];
        //不选
        //f[i][j][k] = max(f[i-1][j][k], f[i][j-1][k]);
        //选
        //f[i][j][k] = max(f[i-1][j][k], f[i][j-1][k]) + x
        //if(k > 0 && x < 0)
        //f[i][j][k] = max(f[i-1][j][k-1], f[i][j-1][k-1])
        for(int[][] x : f){
            for(int[] y : x){
                Arrays.fill(y, Integer.MIN_VALUE/2);
            }
        }
        Arrays.fill(f[0][1], 0);
        //此时f[1][1][k]一定会从f[0][1][k]处转移过来，
        //不会出现-inf这种情况，所以两个选一个赋值为0就行
     	//f[1][j>=1][k] 和 f[i>=1][1][k] 也是同理
        //Arrays.fill(f[1][0], 0);
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                int x = coins[i][j];
                for(int k=0; k<3; k++){
                	//不选的情况和选的第一种情况合起来
                    f[i+1][j+1][k] = Math.max(f[i+1][j][k], f[i][j+1][k]) + x;
                    if(k > 0 && x < 0)
                        f[i+1][j+1][k] = Math.max(f[i+1][j+1][k], Math.max(f[i+1][j][k-1], f[i][j+1][k-1]));
                }
            }
        }
        return f[n][m][2];
    }
}

三、3419. 图的最大边权的最小值

题目链接

本题满足三个条件：

• 所有节点都能到达节点 0，反过来说，从节点 0 可以到所有节点，所以可以反向建图，通过 $dfs(0)$ 计算可以到达的节点个数。
• 图中剩余边的最大边权值尽可能小，就是最大化最小值问题，可以使用二分来做。
• 每个节点至多有 $threshold$ 条出去的边（即出度 $⩽threshold$），这是个干扰条件，由于我们建立的是反图，这里的出度实际上是入度，而在 $dfs(0)$ 遍历的时候，已经保证了所有点的入度为 1，题目也保证了$threshold⩾1$，所以只要能 $dfs(0)$ 遍历到所有节点，这个条件就一定会满足！！！

代码如下：

class Solution {
    public int minMaxWeight(int n, int[][] edges, int t) {
        List<int[]>[] g = new ArrayList[n];
        int mx = 0;
        Arrays.setAll(g, e->new ArrayList<>());
        for(int[] e : edges){
            int x = e[0], y = e[1], w = e[2];
            mx = Math.max(w, mx);
            g[y].add(new int[]{x, w});
        }
        cnt = new int[n];
        int l = 1, r = mx;
        while(l <= r){
            m = (l + r) / 2;
            if(check(g)){
                r = m - 1;
            }else{
                l = m + 1;
            }
        }
        return r + 1 <= mx ? r + 1 : -1;
    }
    //由于每次二分的数字肯定不一样
    //所以可以使用cnt[x] == m 来判断该点是否已经遍历过
    int[] cnt;
    int m;//当前二分的数字
    boolean check(List<int[]>[] g){
        int cnt = dfs(0, g);
        return cnt == g.length;
    }
    int dfs(int x, List<int[]>[] g){
        cnt[x] = m;
        int res = 1;
        for(int[] t : g[x]){
            int y = t[0], w = t[1];
            if(w <= m && cnt[y] != m){
                res += dfs(y, g);
            }
        }
        return res;
    }
}

四、3420. 统计 K 次操作以内得到非递减子数组的数目

题目链接

本题求有多少满足条件的子数组（$k$ 次 $+1$ 操作内，使其变成非递减的子数组），可以使用滑动窗口，枚举右端点 $r$，维护左端点 $l$，设 $cnt$ 为当前 $[l,r]$ 的数组变成非递减所需的最少操作次数。如果 $cnt>k$，需要移动 $l$，直到 $cnt⩽k$，此时以 $r$ 为右端点的满足条件的子数组有 $r-l+1$。

本题的难点在于如何维护 $cnt$:

• 进窗口：将子数组变成非递减需要操作 $t=max(0,max(nums[l:r])-nums[r])$ ，$cnt=cnt+t$，
  • 如何维护区间$[l,r]$最大值，可以使用单调队列 que（维护一个单调递减的序列）来维护。
    • 如果 $\text{que.size() > 0 \&\&}$$nums[que.peekLast()]⩽nums[r+1]$ 时，说明 $nums[que.peekLast()]$ 不可能是当前区间的最大值了，直接删除 $que.pollLast()$，把 $r+1$添加进队列 $que$ 中。
    • 如果 $que.peekFirst()<l$，说明该下标已经不在$[l,r]$区间，直接删除 $que.pollFirst()$。
    • 区间$[l,r]$的最大值为 $nums[que.peekFirst()]$。
• 出窗口：
  

代码如下：

class Solution {
    public long countNonDecreasingSubarrays(int[] nums, int k) {
        int n = nums.length;
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, e->new ArrayList<>());
        Deque<Integer> st = new ArrayDeque<>();
        int[] pos = new int[n];//记录右边第一个大于nums[i]的下标
        Arrays.fill(pos, n);
        for(int i=0; i<n; i++){
            int v = nums[i];
            while(st.size() > 0 && nums[st.peek()] <= v){
                pos[st.pop()] = i;
            }
            if(st.size() > 0){
                g[st.peek()].add(i);//构建上述所说的树
            }
            st.push(i);
        }
        int cnt = 0;
        long ans = 0;
        Deque<Integer> que = new ArrayDeque<>();
        for(int l=0,r=0; r<n; r++){
            int v = nums[r];
            while(que.size() > 0 && nums[que.getLast()] <= v){
                que.removeLast();
            }
            que.addLast(r);
            cnt += Math.max(nums[que.getFirst()] - v, 0);
            while(cnt > k){
                int x = nums[l];
                for(int i : g[l]){
                    if(i > r) break;
                    cnt -= (x - nums[i]) * (Math.min(pos[i], r+1)-i);
                }
                l++;
                if(!que.isEmpty() && que.getFirst() < l)
                    que.removeFirst();
            }
            ans += r - l + 1;
        }
        return ans;
    }
}