前言
上回我们提到区间和，这回来看看最大最小值的问题。
给出一个整型数组A，长度为n，求区间[i, j]即A[i]~A[j]，0<=i<=j<n的最大值与最小值。更进一步地，假如数组可能会改变，又该如何？
观察
基础观察：如何求一个区间内的最大最小值？除了一个个比较外，还有这么一点值得注意——对于区间[i, j]，假如有k个子区间能完全覆盖它且不超出范围，对于每个子区间的最大最小值再取最大最小值，即可得到整个区间的最大最小值。
因为根据定义，以最小值为例，区间[i, j]的最小值意味着找到一个元素A[p]，使得所有其余元素都大于或者等于它。对于这些子区间，找到它们最小值的最小值，即为A[p]。因为对于其余区间，元素值都大于等于其子区间最小值，而该值又大于等于A[p]，由于比较的传递性，该区间所有值也大于等于A[p]。而所有子区间覆盖了[i, j]内的所有元素，所以可证。
需要注意的是子区间要完全覆盖，而且不能超出。完全覆盖确保了每个元素都符合，不然某个漏掉的元素/区间可能会让结果不准确。不能超出避免了区间外元素对结果造成影响，因为原本区间外如何并不影响区间内的结果。
算法
- 暴力破解法
对于每个查询，简单暴力地遍历区间[i, j]然后获取其最大最小值，时间复杂度O(n)，空间复杂度O(1)。数组改变直接更新即可。优点是简单明了，缺点自然是不够高效。代码（由于最大最小值具有对称性，为节约篇幅，大部分时候仅列出一种）：
public int getRangeMinBruteForce(int[] A, int i, int j) {
int ans = Integer.MAX_VALUE;
for (int idx = i; idx <= j; idx++) {
if (A[idx] < ans) ans = A[idx];
}
return ans;
}
- 存储查表法
长度为n的数组有O(n^2)个区间，那么直接预先计算所有区间的结果并存起来，需要的时候查表即可。
预处理需要O(n^2)的时间与空间，查询复杂度O(1)。更新就麻烦了，所有包含更新下标的区间都得跟着更新，复杂度也是O(n^2)。优点是查询快，但是其余的无论是预先计算还是更新，效率都比较差。代码，有点dp的味道：
private int[][] precomputeMin(int[] A) {
int n = A.length;
int[][] lookup = new int[n][n];
// 首先处理长度为1的情况
for (int i = 0; i < n; i++)
lookup[i][i] = A[i];
for (int i = 0; i < n; i++) {
// 然后逐渐从1加长
for (int j = i + 1; j < n; j++)
// 举例：假如我们已经知道A[2,5]的最小值x，那么对于A[6]的值y，假如比x小，那么A[2,6]最小值就为y，否则为x
if (A[lookup[i][j - 1]] < A[j])
lookup[i][j] = lookup[i][j - 1];
else
lookup[i][j] = j;
}
return lookup;
}
public void update(int idx, int newVal, int[] A, int[][] lookup) {
int n = lookup.length;
for (int start = 0; start <= idx; start++)
for (int end = idx; end < n; end++) {
if (newVal < lookup[start][end])
lookup[start][end] = newVal;
}
A[idx] = newVal;
}
- 平方根分解法(Square Root Decomposition)
这是对于法2的改进。假如把数组分成长度为n^(1/2)即根号n的一段段，最多有(根号n)+1组，最后一组可能不满但是不太影响（比如n=10，根号n=3，分为4组，最后1组1个元素）。分别计算每一段的结果，这样预先计算其实还是O(n)，空间复杂度O(n^1/2)。查询的时候，假设范围[i, j]覆盖了m个根号n区间，然后两侧各有一段没有被完全覆盖。因为整个数组也只有(根号n)+1组，所以m不可能比这还大，因此m个区间直接比较它们的结果就可以获得中间的结果，复杂度为O(m)=O(根号n)。至于边上的，则线性扫描过去，由于区间长度也最多为根号n，两边扫描复杂度也是根号n，因此查询的整体复杂度就是O(n^1/2)。更新只需更新对应区间即可，O(1)。代码其实还没有想象中那么简单：
private int[] squareRootDecompositionMinPreCalculate(int[] A) {
int n = A.length, r = (int) Math.sqrt(n), len = (int) Math.ceil((double) n / r);
int[] mat = new int[len];
int p = 0;
while (p < len) {
int min = Integer.MAX_VALUE;
for (int i = p * r; i < Math.min((p + 1) * r, n); i++) {
if (A[i] < min) min = A[i];
}
mat[p++] = min;
}
return mat;
}
public int squareRootDecompositionMin(int[] A, int i, int j, int[] mat) {
int n = A.length, r = (int) Math.sqrt(n);
// 对于某个idx，其区间序列为idx/r，那么该区间开始的下标为(idx/r)*r，结束的下标为min(n, (idx/r)*r + r) - 1
// start和end指向i到j包含的完整子区间序列
int start = i % r == 0 ? i / r : i / r + 1, end = j / r - 1;
int ans = Integer.MAX_VALUE;
for (int k = start; k <= end; k++) {
if (mat[k] < ans) ans = mat[k];
}
// 扫描两侧剩余部分
for (int k = i; k <= Math.min(j, (i / r) * r + r - 1); k++) {
if (A[k] < ans) ans = A[k];
}
for (int k = j; k >= Math.max(i, (j / r) * r); k--) {
if (A[k] < ans) ans = A[k];
}
return ans;
}
public void update(int idx, int newVal, int[] A, int[] mat) {
int n = A.length, r = (int) Math.sqrt(n);
if (mat[idx / r] > newVal) mat[idx / r] = newVal;
A[idx] = newVal;
}
-
离散表法(Sparse Table Algorithm)
延续法3的思路，查询可以变得更高效。
仍以最小值为例，现在使用这样一个二维数组lookup[][]，lookup[i][j]代表从下标i开始的长度为2^j的区间的最小值。例如lookup[0][3]代表了从下标0开始，长度为2^3=8的区间，即[0, 7]。假如超出了数组最大长度，则不存。
这样有什么好处呢？
image.png
现在有区间[i,j]长度为L=j-i+1，我们获取一个最大的k使得2^k<=L而2^(k+1)>L。这样，考虑两个子区间
[i, i + 2^k-1]与[j - 2^k + 1,j]，根据定义这两个子区间必定重合，否则说明2*(2^k)<=L与假设不符。还记得基础观察部分吗？这两个子区间的最小值即为整个区间的最小值。Q(i,j)=min(lookup[i][k], lookup[j-2^k+1][k])。
也就是说，假如我们已经算好了lookup，查询只需要一次比较，加上一点k的计算（可以用log算出），时间复杂度为O(1)。
再来看看如何计算lookup。这有点类似于法2的计算，首先把长度为1的部分都填好，接下来每次长度乘以2.假如我们已经填好2^(j-1)的部分了，对于lookup[i][j]，可以分为长度为2^(j-1)的2部分，即[i, i+2^(j-1)-1]与[i+2^(j-1), i+2^j-1]，从lookup上来看就是lookup[i][j-1]与lookup[i+2^(j-1)][j-1]。也就是说：lookup[i][j]=min(lookup[i][j-1],lookup[i+2^(j-1)][j-1])。
显然，这种预先计算需要O(nlogn)的时间与空间复杂度。
更新对于这种方法来说也不容易，基本上是推倒了重算，O(nlogn)。因此，这种方法更适合数组不变的情况。代码：
private int[][] precomputeSparseTable(int[] A) {
int n = A.length, m = log2(n);
int[][] lookup = new int[n][m];
// 先处理长度为1
for (int i = 0; i < n; i++)
lookup[i][0] = A[i];
// 1<<j=2^j
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; (i + (1 << j) - 1) < n; i++) {
lookup[i][j] = Math.min(lookup[i][j - 1], lookup[i + (1 << (j - 1))][j - 1]);
}
}
return lookup;
}
public int getSparseTableMin(int i, int j, int[][] lookup) {
int k = log2(j - i + 1);
return Math.min(lookup[i][k], lookup[j - (1 << k) + 1][k]);
}
private int log2(int N) {
return (int) (Math.log(N) / Math.log(2));
}
- 线段树
既然线段树能用来解决区间和，自然也能用来解决区间最大最小值，无非是把求和操作变成了求最大最小值而已。创建O(nlogn)，查询和更新都是O(logn)，空间O(n)。可见优点是更新较快，缺点自然是查询不算最快的。因此假如需要频繁更新，也可以考虑这种数据结构。
public class MinMaxSegmentTree {
private static class TreeNode {
int start, end, min, max;
TreeNode left, right;
TreeNode(int start, int end) {
this.start = start;
this.end = end;
}
}
private TreeNode buildTree(int[] nums, int start, int end) {
if (start > end) return null;
TreeNode cur = new TreeNode(start, end);
if (start == end) {
cur.min = nums[start];
cur.max = nums[start];
} else {
int mid = start + (end - start) / 2;
cur.left = buildTree(nums, start, mid);
cur.right = buildTree(nums, mid + 1, end);
cur.min = Math.min(cur.left.min, cur.right.min);
cur.max = Math.max(cur.left.max, cur.right.max);
}
return cur;
}
private void updateTree(TreeNode node, int i, int val) {
if (node.start == node.end) {
node.min = val;
node.max = val;
} else {
int mid = node.start + (node.end - node.start) / 2;
if (i <= mid) updateTree(node.left, i, val);
else updateTree(node.right, i, val);
node.min = Math.min(node.left.min, node.right.min);
node.max = Math.max(node.left.max, node.right.max);
}
}
private int queryTree(TreeNode node, int i, int j, boolean min) {
if (node.start == i && node.end == j) return min ? node.min : node.max;
else {
int mid = node.start + (node.end - node.start) / 2;
if (j <= mid) {
return queryTree(node.left, i, j, min);
} else if (i >= (mid + 1)) {
return queryTree(node.right, i, j, min);
} else {
int left = queryTree(node.left, i, mid, min), right = queryTree(node.right, mid + 1, j, min);
return min ? Math.min(left, right) : Math.max(left, right);
}
}
}
TreeNode root;
MinMaxSegmentTree(int[] nums) {
root = buildTree(nums, 0, nums.length - 1);
}
public void update(int i, int val) {
updateTree(root, i, val);
}
public int queryMin(int i, int j) {
return queryTree(root, i, j, true);
}
public int queryMax(int i, int j) {
return queryTree(root, i, j, false);
}
}
