|
滑动窗口是什么？
滑动窗口是一种想象出来的数据结构：
滑动窗口有左边界L和有边界R
在数组或者字符串或者一个序列上，记为S，窗口就是S[L..R]这一部分
L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口
L和R都只能往右滑
滑动内最大值和最小值的更新结构
窗口不管L还是R滑动之后，都会让窗口呈现新状况，
如何能够更快的得到窗口当前状况下的最大值和最小值？
最好平均下来复杂度能做到O(1)
利用单调双端队列！
?题目一
假设一个固定大小为W的窗口，依次划过arr，
返回每一次滑出状况的最大值
例如，arr = [4,3,5,4,3,3,6,7], W = 3
返回：[5,5,5,4,6,7]
public static int[] getMaxWindow(int[] arr, int w) {
if (arr == null || w < 1 || arr.length < w) {
return null;
}
// qmax 窗口最大值的更新结构
// 放下标
LinkedList<Integer> qmax = new LinkedList<Integer>();
int[] res = new int[arr.length - w + 1];
int index = 0;
for (int R = 0; R < arr.length; R++) {
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
qmax.pollLast();
}
qmax.addLast(R);
if (qmax.peekFirst() == R - w) {
qmax.pollFirst();
}
if (R >= w - 1) {
res[index++] = arr[qmax.peekFirst()];
}
}
return res;
}
?题目二
?给定一个整型数组arr，和一个整数num
某个arr中的子数组sub，如果想达标，必须满足：
sub中最大值 – sub中最小值 <= num，
返回arr中达标子数组的数量
public static int num(int[] arr, int sum) {
if (arr == null || arr.length == 0 || sum < 0) {
return 0;
}
int N = arr.length;
int count = 0;
LinkedList<Integer> maxWindow = new LinkedList<>();
LinkedList<Integer> minWindow = new LinkedList<>();
int R = 0;
for (int L = 0; L < N; L++) {
while (R < N) {
while (!maxWindow.isEmpty() && arr[maxWindow.peekLast()] <= arr[R]) {
maxWindow.pollLast();
}
maxWindow.addLast(R);
while (!minWindow.isEmpty() && arr[minWindow.peekLast()] >= arr[R]) {
minWindow.pollLast();
}
minWindow.addLast(R);
if (arr[maxWindow.peekFirst()] - arr[minWindow.peekFirst()] > sum) {
break;
} else {
R++;
}
}
count += R - L;
if (maxWindow.peekFirst() == L) {
maxWindow.pollFirst();
}
if (minWindow.peekFirst() == L) {
minWindow.pollFirst();
}
}
return count;
}
题目三
https://leetcode.com/problems/gas-station
?加油站的良好出发点问题
数组A表示加油站能加多少油，数组B表示加油站到下一个加油站锁消耗多少油
// 这个方法的时间复杂度O(N)，额外空间复杂度O(N)
public static int canCompleteCircuit(int[] gas, int[] cost) {
boolean[] good = goodArray(gas, cost);
for (int i = 0; i < gas.length; i++) {
if (good[i]) {
return i;
}
}
return -1;
}
public static boolean[] goodArray(int[] g, int[] c) {
int N = g.length;
int M = N << 1;
int[] arr = new int[M];
for (int i = 0; i < N; i++) {
arr[i] = g[i] - c[i];
arr[i + N] = g[i] - c[i];
}
for (int i = 1; i < M; i++) {
arr[i] += arr[i - 1];
}
LinkedList<Integer> w = new LinkedList<>();
for (int i = 0; i < N; i++) {
while (!w.isEmpty() && arr[w.peekLast()] >= arr[i]) {
w.pollLast();
}
w.addLast(i);
}
boolean[] ans = new boolean[N];
for (int offset = 0, i = 0, j = N; j < M; offset = arr[i++], j++) {
if (arr[w.peekFirst()] - offset >= 0) {
ans[i] = true;
}
if (w.peekFirst() == i) {
w.pollFirst();
}
while (!w.isEmpty() && arr[w.peekLast()] >= arr[j]) {
w.pollLast();
}
w.addLast(j);
}
return ans;
}
题目四
arr是货币数组，其中的值都是正数。再给定一个正数aim。
每个值都认为是一张货币，
返回组成aim的最少货币数
注意：
因为是求最少货币数，所以每一张货币认为是相同或者不同就不重要了
?
// dp1时间复杂度为：O(arr长度 * aim)
public static int dp1(int[] arr, int aim) {
if (aim == 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 0;
for (int j = 1; j <= aim; j++) {
dp[N][j] = Integer.MAX_VALUE;
}
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
int p1 = dp[index + 1][rest];
int p2 = rest - arr[index] >= 0 ? dp[index + 1][rest - arr[index]] : Integer.MAX_VALUE;
if (p2 != Integer.MAX_VALUE) {
p2++;
}
dp[index][rest] = Math.min(p1, p2);
}
}
return dp[0][aim];
}
?
public static class Info {
public int[] coins;
public int[] zhangs;
public Info(int[] c, int[] z) {
coins = c;
zhangs = z;
}
}
public static Info getInfo(int[] arr) {
HashMap<Integer, Integer> counts = new HashMap<>();
for (int value : arr) {
if (!counts.containsKey(value)) {
counts.put(value, 1);
} else {
counts.put(value, counts.get(value) + 1);
}
}
int N = counts.size();
int[] coins = new int[N];
int[] zhangs = new int[N];
int index = 0;
for (Entry<Integer, Integer> entry : counts.entrySet()) {
coins[index] = entry.getKey();
zhangs[index++] = entry.getValue();
}
return new Info(coins, zhangs);
}
// dp2时间复杂度为：O(arr长度) + O(货币种数 * aim * 每种货币的平均张数)
public static int dp2(int[] arr, int aim) {
if (aim == 0) {
return 0;
}
// 得到info时间复杂度O(arr长度)
Info info = getInfo(arr);
int[] coins = info.coins;
int[] zhangs = info.zhangs;
int N = coins.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 0;
for (int j = 1; j <= aim; j++) {
dp[N][j] = Integer.MAX_VALUE;
}
// 这三层for循环，时间复杂度为O(货币种数 * aim * 每种货币的平均张数)
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
dp[index][rest] = dp[index + 1][rest];
for (int zhang = 1; zhang * coins[index] <= aim && zhang <= zhangs[index]; zhang++) {
if (rest - zhang * coins[index] >= 0
&& dp[index + 1][rest - zhang * coins[index]] != Integer.MAX_VALUE) {
dp[index][rest] = Math.min(dp[index][rest], zhang + dp[index + 1][rest - zhang * coins[index]]);
}
}
}
}
return dp[0][aim];
}
// dp3时间复杂度为：O(arr长度) + O(货币种数 * aim)
// 优化需要用到窗口内最小值的更新结构
public static int dp3(int[] arr, int aim) {
if (aim == 0) {
return 0;
}
// 得到info时间复杂度O(arr长度)
Info info = getInfo(arr);
int[] c = info.coins;
int[] z = info.zhangs;
int N = c.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 0;
for (int j = 1; j <= aim; j++) {
dp[N][j] = Integer.MAX_VALUE;
}
// 虽然是嵌套了很多循环，但是时间复杂度为O(货币种数 * aim)
// 因为用了窗口内最小值的更新结构
for (int i = N - 1; i >= 0; i--) {
for (int mod = 0; mod < Math.min(aim + 1, c[i]); mod++) {
// 当前面值 X
// mod mod + x mod + 2*x mod + 3 * x
LinkedList<Integer> w = new LinkedList<>();
w.add(mod);
dp[i][mod] = dp[i + 1][mod];
for (int r = mod + c[i]; r <= aim; r += c[i]) {
while (!w.isEmpty() && (dp[i + 1][w.peekLast()] == Integer.MAX_VALUE
|| dp[i + 1][w.peekLast()] + compensate(w.peekLast(), r, c[i]) >= dp[i + 1][r])) {
w.pollLast();
}
w.addLast(r);
int overdue = r - c[i] * (z[i] + 1);
if (w.peekFirst() == overdue) {
w.pollFirst();
}
dp[i][r] = dp[i + 1][w.peekFirst()] + compensate(w.peekFirst(), r, c[i]);
}
}
}
return dp[0][aim];
}
|