[每日两题系列]刷算法题咯~~

        本系列所选题目均来自力扣或者牛客网站. 所选题目主要是以其中的简单题为主, 中等题为辅, 包含少数困难题(原因是: 本人目前能力还不够~ ). 开展这个系列的目的是督促自己, 在暑假的时间里也要保持有一定的刷题量, 拒绝摆烂~
        话不多说, 直接开刷~~ 今天做的两道题都比较难想(难度为中等上的题目).

最多能完成排序的块II

        题目描述: arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。最多能将数组分成多少块？

• 示例1:
  输入: arr = [5,4,3,2,1]
  输出: 1
  解释: 将数组分成2块或者更多块，都无法得到所需的结果。例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。

• 示例2:
  输入: arr = [2,1,3,4,4]
  输出: 4
  解释: 我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

解题思路:
        (1) 在这道题中, 我们可以先考虑一下两个极端: 1. 当所给的数组是有序的时候, 那么我们要分成最多块就可以是每个元素都是独立的一块; 2. 当所给的数组是逆序的时候, 那么我们就只能将其分在同一块中, 因为如果分在不同块的话, 都会是不成立的.
        (2) 由上面的两种极端情况我们就可以推出一个结论: 当前面已经分好的组当中的最大值存在有比准备要加入的值还要大的话, 那么就需要从这个组开始到准备要加入值的这整个区间都合并成一个组(举个例子: 一个子数组: [4, 5, 3], 一开始4和肯定是分在不同的组里面的, 但是3加入进来了, 由于3比4小, 所以就会把这整个子数组合并成一个组); 否则直接新开一个组, 然后继续遍历后面的值直到遍历完, 这时候就可以把这个数组中的元素分成最多的组.
        (3) 通过上面的思路, 接下来我们就可以来确定代码应该如何写了, 由于我们遍历到的每个元素都只是和每个组中的最大值作比较, 也就是说我们只需要将每个组中的最大值存起来就可以了, 这时候我们就可以想到使用栈来实现, 当栈不为空同时栈顶元素大于准备加入的元素, 那么说明这个元素可以和栈顶元素组成一组, 这时候我们就需要更新栈顶元素, 循环执行, 直到栈为空或者是栈顶元素小于等于准备加入的元素, 则说明这个元素是可以自成一组的, 直接将这个元素加入到栈中即可.
        (4) 最后, 这个栈中的元素个数就是最多的块数.

实现代码:

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        for(int x : arr){
            int t = x;
            while(!stack.empty() && stack.peek() > x){
                t = Math.max(stack.peek(), t);
                stack.pop();
            }
            stack.push(t);
        }
        return stack.size();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

统计子矩阵

        题目描述: 给定一个 N×M 的矩阵 A，请你统计有多少个子矩阵 (最小 1×1，最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K?
        输入格式: 第一行包含三个整数 N,M 和 K。之后 N 行每行包含 M 个整数，代表矩阵 A。
        输出格式: 一个整数代表答案。

• 示例:
  输入：
  3 4 10
  1 2 3 4
  5 6 7 8
  9 10 11 12
  输出：
  19
  解释: 满足条件的子矩阵一共有 19，包含：
  大小为 1×1 的有 10 个。
  大小为 1×2 的有 3 个。
  大小为 1×3 的有 2 个。
  大小为 1×4 的有 1 个。
  大小为 2×1 的有 3 个。

解题思路:
        (1) 这道题如果直接使用暴力的做法: 也就是定义四个边界所围成的范围中的和与 k 作比较, 那么此时的时间复杂度为 O(n^4), 这样的时间复杂度可能会超过时间限制. 下面来介绍一种时间复杂度为 O(n^3) 的做法.
        (2) 我们要想把时间复杂度给降下来, 就需要将这个二维矩阵变成一个一维的矩阵, 我们就可以假设在同一个行区间中, 我们只需要定义一个双指针来依次找到符合条件的子矩阵, 这样就可以成功把时间复杂度给降下来了.
        (3) 要想使用上面这个思想, 我们先将每一列上的元素做一个前缀和, 这样就可以保证在子矩阵扩大的时候, 依旧可以是一维的, 因为这个双指针依旧还是在对一行进行操作的. 依据这个思路, 我们就可以编写出下面的这段代码.

实现代码:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        int[][] array = new int[n+1][m+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                array[i][j] = scanner.nextInt() + array[i-1][j];
            }
        }
        long ret = 0;
        for(int i = 1; i <= n; i++){
            for(int j = i; j <= n; j++){
                int left = 1;
                int right = 1;
                int sum = 0;
                for(;right <= m; right++){
                    sum += array[j][right] - array[i-1][right];
                    while(sum > k){
                        sum -= array[j][left] - array[i-1][left];
                        left++;
                    }
                    ret += right - left + 1;
                }
            }
        }
        System.out.println(ret);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33