滑动窗口
有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如，数组为 [4, 3, 5, 4, 3, 3, 6, 7]，窗口大小为 3 时:
[4 3 5] 4 3 3 6 7 // 窗口中最大值为 54 [3 5 4] 3 3 6 7 // 窗口中最大值为 54 3 [5 4 3] 3 6 7 // 窗口中最大值为 54 3 5 [4 3 3] 6 7 // 窗口中最大值为 44 3 5 4 [3 3 6] 7 // 窗口中最大值为 64 3 5 4 3 [3 6 7] // 窗口中最大值为 7
如果数组长度为 n，窗口大小为 w，则一共产生 n-w+1 个窗口的最大值。
请实现一个函数。
输入：整型数组 arr，窗口大小为 w。
输出：一个长度为 n-w+1 的数组 res，res[i] 表示每一种窗口状态下的最大值。以本题为例，结果应该返回{5, 5, 5, 4, 6, 7]。
简单解法：每次都使用下标遍历找到求再窗口内最大的值，代码略
思路：
维护一个队列，每次窗口滑动时新增按顺序加入，每次新加入值时都保证整个队列中是单调递增的，最大值永远在队列的头部
代码实现
import java.util.Arrays;import java.util.LinkedList;public class SlidingWindowMaxArray {static int[] getMax(int[] arr, int w) {if (arr == null || w < 1 || arr.length < w) return null;// Java 中的双端队列就是 LinkedListLinkedList<Integer> queue = new LinkedList<>();int[] res = new int[arr.length - w + 1];for (int i = 0; i < arr.length; i++) {// 当队尾的元素 < 当前元素时 弹出while (!queue.isEmpty() && arr[queue.peekLast()] < arr[i]) {queue.pollLast();}queue.add(i);// 当队头的元素下标不在范围内时弹出while (i - queue.peekFirst() >= w) {queue.pollFirst();}if (i >= w - 1) {res[i - w + 1] = arr[queue.peekFirst()];}}return res;}public static void main(String[] args) {System.out.println(Arrays.toString(getMax(new int[]{4, 3, 5, 4, 3, 3, 6, 7}, 3)));}}
结果
[5, 5, 5, 4, 6, 7]
单调栈
在数组中想找到一个数，左边和右边比这个数大、且离这个数最近的位置。
如果对每一个数都想求这样的信息，能不能整体代价达到
？
简单解法：从 i 位置向两侧遍历，直到比 arr[i] 大的数或者遍历结束。代码略，复杂度为 
思路：
假设，数组中没有重复的数。如下图
依次将将数据放入栈中，保持栈是单调递减的，下标 0、1、2 的数都能放入栈中
但是在放下标 3 数据时破坏栈的单调性，此时就弹出栈顶元素，直到栈能保持单调。
弹出的元素就可以知道该元素的左右两侧比该元素大的值：左侧：当前栈顶；右侧：当前数，如下图：
同理，可以得到其他数据的结果
剩下的两个略…… 懒得画了
如果有重复的数字，可以将栈中元素变成 List，将相同的元素放到 List 中。
代码实现
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class LargerNumOnBothSides {
static int[][] findNums(int[] arr) {
if (arr == null || arr.length == 0) return null;
int[][] res = new int[arr.length][2];
Stack<List<Integer>> stack = new Stack<>();
stack.push(new ArrayList<Integer>() {{
add(0);
}});
for (int i = 1; i < arr.length; i++) {
while (!stack.isEmpty() && arr[stack.peek().get(0)] < arr[i]) {
getRes(res, stack, i);
}
List<Integer> list = null;
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
list = stack.peek();
} else {
list = new ArrayList<>();
}
list.add(i);
stack.push(list);
}
while (!stack.isEmpty()) {
getRes(res, stack, -1);
}
return res;
}
private static void getRes(int[][] res, Stack<List<Integer>> stack, int i) {
List<Integer> list = stack.pop();
for (Integer index : list) {
Integer left = stack.isEmpty() ? -1 : stack.peek().get(0);
res[index] = new int[]{left, i};
}
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 6, 1, 2, 0, 7};
int[][] nums = findNums(arr);
for (int i = 0; i < nums.length; i++) {
String left = nums[i][0] == -1 ? "null" : String.valueOf(arr[nums[i][0]]);
String rifht = nums[i][1] == -1 ? "null" : String.valueOf(arr[nums[i][1]]);
System.out.println(arr[i] + "\t左侧：" + left + "\t右侧：" + rifht);
}
System.out.println("####################");
arr = new int[]{5, 4, 3, 4, 5, 3, 6};
nums = findNums(arr);
for (int i = 0; i < nums.length; i++) {
String left = nums[i][0] == -1 ? "null" : String.valueOf(arr[nums[i][0]]);
String rifht = nums[i][1] == -1 ? "null" : String.valueOf(arr[nums[i][1]]);
System.out.println(arr[i] + "\t左侧：" + left + "\t右侧：" + rifht);
}
}
}
结果
5 左侧：null 右侧：6
4 左侧：5 右侧：6
3 左侧：4 右侧：6
6 左侧：null 右侧：7
1 左侧：6 右侧：2
2 左侧：6 右侧：7
0 左侧：2 右侧：7
7 左侧：null 右侧：null
####################
5 左侧：null 右侧：6
4 左侧：5 右侧：5
3 左侧：4 右侧：4
4 左侧：5 右侧：5
5 左侧：null 右侧：6
3 左侧：5 右侧：6
6 左侧：null 右侧：null
应用
定义：一个正数数组，数组中累加和与最小值的乘积，假设叫做指标 A。
给定一个数组，返回子数组中指标 A 最大的值。
思路：指标 A 要最大，A = 累加和 * 最小值，就可以遍历求出每个下标 i 为最小值的子数组最大 A。
如：数组 [5,3,2,1,6,7,8,4]
- i = 0，子数组为 以 5 为最小值的子数组为
[5]A = 5*5 = 25 - i = 1，以 3 为最小值的子数组可为
[3]A = 3*3 = 9[5,3]A = (5+3)*3 = 24
- i = 2，以 2 为最小值的子数组可为
[2]A = 2*2 = 4[3,2]A = (3+2)*2 = 10[5,3,2]A = (5+3+2)*2 = 20
- 综上，应该选择子数组长度最大的，以
arr[i]为最小值的子数组 - i = 3，以 1 为最小值的长度最大的子数组为
[5,3,2,1,6,7,8,4]…… - ……
观察可得到规律：选择子数组长度最大的，以 arr[i] 为最小值的子数组。就是选择 arr[i] 两侧比 arr[i] 小的值为边界的子数组，如下图：
即，使用单调栈找到 arr[i] 两侧比该数小的下标就能得到最大的 A 指标
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class MaxA {
static int findMaxA(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int maxA = 0;
Stack<List<Integer>> stack = new Stack<>();
stack.push(new ArrayList<Integer>() {{
add(0);
}});
for (int i = 1; i < arr.length; i++) {
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
maxA = Math.max(getRes(arr, stack, i), maxA);
}
List<Integer> list = null;
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
list = stack.peek();
} else {
list = new ArrayList<>();
}
list.add(i);
stack.push(list);
}
while (!stack.isEmpty()) {
maxA = Math.max(getRes(arr, stack, arr.length), maxA);
}
return maxA;
}
private static int getRes(int[] arr, Stack<List<Integer>> stack, int i) {
int cur = arr[stack.pop().get(0)];
int left = stack.isEmpty() ? -1 : stack.peek().get(0);
int right = i;
int sum = 0;
for (int index = left + 1; index < right; index++) {
sum += arr[index];
}
return sum * cur;
}
public static void main(String[] args) {
int[] arr = {5, 3, 2, 1, 6, 7, 8, 4};
System.out.println(Arrays.toString(arr));
System.out.println(findMaxA(arr));
}
}
结果
[5, 3, 2, 1, 6, 7, 8, 4]
126
若有收获，就点个赞吧
0 人点赞
