前言
上回我們提到區(qū)間和，這回來看看最大最小值的問題。
給出一個整型數(shù)組A，長度為n，求區(qū)間[i, j]即A[i]~A[j]，0<=i<=j<n的最大值與最小值。更進(jìn)一步地，假如數(shù)組可能會改變，又該如何？
觀察
基礎(chǔ)觀察：如何求一個區(qū)間內(nèi)的最大最小值？除了一個個比較外，還有這么一點值得注意——對于區(qū)間[i, j]，假如有k個子區(qū)間能完全覆蓋它且不超出范圍，對于每個子區(qū)間的最大最小值再取最大最小值，即可得到整個區(qū)間的最大最小值。
因為根據(jù)定義，以最小值為例，區(qū)間[i, j]的最小值意味著找到一個元素A[p]，使得所有其余元素都大于或者等于它。對于這些子區(qū)間，找到它們最小值的最小值，即為A[p]。因為對于其余區(qū)間，元素值都大于等于其子區(qū)間最小值，而該值又大于等于A[p]，由于比較的傳遞性，該區(qū)間所有值也大于等于A[p]。而所有子區(qū)間覆蓋了[i, j]內(nèi)的所有元素，所以可證。
需要注意的是子區(qū)間要完全覆蓋，而且不能超出。完全覆蓋確保了每個元素都符合，不然某個漏掉的元素/區(qū)間可能會讓結(jié)果不準(zhǔn)確。不能超出避免了區(qū)間外元素對結(jié)果造成影響，因為原本區(qū)間外如何并不影響區(qū)間內(nèi)的結(jié)果。
算法
- 暴力破解法
對于每個查詢，簡單暴力地遍歷區(qū)間[i, j]然后獲取其最大最小值，時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。數(shù)組改變直接更新即可。優(yōu)點是簡單明了，缺點自然是不夠高效。代碼（由于最大最小值具有對稱性，為節(jié)約篇幅，大部分時候僅列出一種）：
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的數(shù)組有O(n^2)個區(qū)間，那么直接預(yù)先計算所有區(qū)間的結(jié)果并存起來，需要的時候查表即可。
預(yù)處理需要O(n^2)的時間與空間，查詢復(fù)雜度O(1)。更新就麻煩了，所有包含更新下標(biāo)的區(qū)間都得跟著更新，復(fù)雜度也是O(n^2)。優(yōu)點是查詢快，但是其余的無論是預(yù)先計算還是更新，效率都比較差。代碼，有點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++)
// 舉例：假如我們已經(jīng)知道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的改進(jìn)。假如把數(shù)組分成長度為n^(1/2)即根號n的一段段，最多有(根號n)+1組，最后一組可能不滿但是不太影響（比如n=10，根號n=3，分為4組，最后1組1個元素）。分別計算每一段的結(jié)果，這樣預(yù)先計算其實還是O(n)，空間復(fù)雜度O(n^1/2)。查詢的時候，假設(shè)范圍[i, j]覆蓋了m個根號n區(qū)間，然后兩側(cè)各有一段沒有被完全覆蓋。因為整個數(shù)組也只有(根號n)+1組，所以m不可能比這還大，因此m個區(qū)間直接比較它們的結(jié)果就可以獲得中間的結(jié)果，復(fù)雜度為O(m)=O(根號n)。至于邊上的，則線性掃描過去，由于區(qū)間長度也最多為根號n，兩邊掃描復(fù)雜度也是根號n，因此查詢的整體復(fù)雜度就是O(n^1/2)。更新只需更新對應(yīng)區(qū)間即可，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，其區(qū)間序列為idx/r，那么該區(qū)間開始的下標(biāo)為(idx/r)*r，結(jié)束的下標(biāo)為min(n, (idx/r)*r + r) - 1
// start和end指向i到j(luò)包含的完整子區(qū)間序列
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];
}
// 掃描兩側(cè)剩余部分
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)
延續(xù)法3的思路，查詢可以變得更高效。
仍以最小值為例，現(xiàn)在使用這樣一個二維數(shù)組lookup[][]，lookup[i][j]代表從下標(biāo)i開始的長度為2^j的區(qū)間的最小值。例如lookup[0][3]代表了從下標(biāo)0開始，長度為2^3=8的區(qū)間，即[0, 7]。假如超出了數(shù)組最大長度，則不存。
這樣有什么好處呢？
image.png
現(xiàn)在有區(qū)間[i,j]長度為L=j-i+1，我們獲取一個最大的k使得2^k<=L而2^(k+1)>L。這樣，考慮兩個子區(qū)間
[i, i + 2^k-1]與[j - 2^k + 1,j]，根據(jù)定義這兩個子區(qū)間必定重合，否則說明2*(2^k)<=L與假設(shè)不符。還記得基礎(chǔ)觀察部分嗎？這兩個子區(qū)間的最小值即為整個區(qū)間的最小值。Q(i,j)=min(lookup[i][k], lookup[j-2^k+1][k])。
也就是說，假如我們已經(jīng)算好了lookup，查詢只需要一次比較，加上一點k的計算（可以用log算出），時間復(fù)雜度為O(1)。
再來看看如何計算lookup。這有點類似于法2的計算，首先把長度為1的部分都填好，接下來每次長度乘以2.假如我們已經(jīng)填好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])。
顯然，這種預(yù)先計算需要O(nlogn)的時間與空間復(fù)雜度。
更新對于這種方法來說也不容易，基本上是推倒了重算，O(nlogn)。因此，這種方法更適合數(shù)組不變的情況。代碼：
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));
}
- 線段樹
既然線段樹能用來解決區(qū)間和，自然也能用來解決區(qū)間最大最小值，無非是把求和操作變成了求最大最小值而已。創(chuàng)建O(nlogn)，查詢和更新都是O(logn)，空間O(n)?？梢妰?yōu)點是更新較快，缺點自然是查詢不算最快的。因此假如需要頻繁更新，也可以考慮這種數(shù)據(jù)結(jié)構(gòu)。
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);
}
}
