【算法笔记】单调栈
·
1、单调栈
- 单调栈：单调栈是指栈中的元素从栈底到栈顶是单调递增或单调递减的栈。
- 比如我们常用的单调递增的栈，栈中的元素从栈底到栈顶是单调递增的，
- 在入栈一个数的时候，要判断这个数和栈顶元素的大小，如果栈顶元素是大于等于这个数的，要将栈顶元素弹出，直到栈顶元素小于这个数。然后将这个数入栈。
- 也就是说，在需要入栈一个数的时候，这个数是必须要入的，但是要把之前比它大的数弹出。
- 这样做的好处就是：在入栈一个数x的时候，如果要将栈中的元素弹出，加入要弹出的这个数是b，那就说明x是b右边比它小的第一个数。
- 同时，如果栈里面还有一个元素为c，说明c是b左边比它小的第一个数。
- 所以在弹出b的时候，我们可以计算找到其入站顺序的左边和右边比它小的第一个数分别是c和x。
- 同时也可可以得出：在c右边一个数和x左边一个数(也就是不包含c和x)之间的所有数都比b大。b是(c,x)之间的最小值。
- 这个在柱状图中或者找数组最小值的情况下是很常用的，
- 具体看后面的题目。
2、单调栈相关题目
2.1、题目一：求数组的每个位置左右两侧离其最近且比其小的数
2.1.1 暴力方法实现的对数器
- 暴力方法实现的对数器
- 思路：
- 到每一个位置，到左右两侧遍历去获取比它小的值。
/**
* 暴力方法实现的对数器
* 思路：
* 到每一个位置，到左右两侧遍历去获取比它小的值。
*/
public static int[][] comparator(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0][2];
}
int[][] res = new int[arr.length][2];
// 循环每个位置
for (int i = 0; i < arr.length; i++) {
// 找到左侧最小值
int leftLessIndex = -1;
// 从i左侧第一个开始
int cur = i - 1;
while (cur >= 0) {
// 找到第一个小的，就退出循环
if (arr[cur] < arr[i]) {
leftLessIndex = cur;
break;
}
cur--;
}
// 找到右侧最小值
int rightLessIndex = -1;
// 从i右侧第一个开始
cur = i + 1;
while (cur < arr.length) {
// 找到第一个小的，就退出循环
if (arr[cur] < arr[i]) {
rightLessIndex = cur;
break;
}
cur++;
}
res[i][0] = leftLessIndex;
res[i][1] = rightLessIndex;
}
return res;
}
2.1.2 没有重复值的数组单调栈的应用方法
- 没有重复值的数组单调栈的应用方法。
- 思路：
- 对于没有重复值的数组来说，应用单调栈的方法能很快找出其左右两侧最近的最小值。
- 我们准备一个单调递增的栈，依次将元素加入到栈中，在加入一个元素的时候，如果栈顶元素大于当前的元素，就将其出栈，此时右侧的最小值就是让它出栈的值，
- 左侧的最小值就是此时栈中的栈顶元素。如果此时栈中已经没有元素了，说明没有左侧的最小值。
- 当所有元素都循环一遍以后，栈中还有值，要将栈中的值依次出栈，此时右侧没有最小值，左侧最小值依然是当前值出栈以后的栈顶元素，如果栈中没有，说明也没有左侧最小值。
/**
* 没有重复值的数组单调栈的应用方法。
* 思路：
* 对于没有重复值的数组来说，应用单调栈的方法能很快找出其左右两侧最近的最小值。
* 我们准备一个单调递增的栈，依次将元素加入到栈中，在加入一个元素的时候，如果栈顶元素大于当前的元素，就将其出栈，此时右侧的最小值就是让它出栈的值，
* 左侧的最小值就是此时栈中的栈顶元素。如果此时栈中已经没有元素了，说明没有左侧的最小值。
* 当所有元素都循环一遍以后，栈中还有值，要将栈中的值依次出栈，此时右侧没有最小值，左侧最小值依然是当前值出栈以后的栈顶元素，如果栈中没有，说明也没有左侧最小值。
*/
public static int[][] getNearLessNoRepeat(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0][2];
}
int[][] res = new int[arr.length][2];
Stack<Integer> stack = new Stack<>();
// 将所有元素依次入栈,栈中保存的是下标，不是真正的值
for (int i = 0; i < arr.length; i++) {
// 将栈中大于目前值的出栈，并结算出栈的下标的左右最小值，填充到结果数组中
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
// 要结算的下标是第一个出栈的值
int curIndex = stack.pop();
// 左侧小值是此时栈顶元素，如果没有就是没有左侧最小值
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[curIndex][0] = leftLessIndex;
// 右侧的小值就是让其出栈的值
res[curIndex][1] = i;
}
// 所有大于当前值的都出栈结算后，当前的下标要入栈
stack.push(i);
}
// 栈中还有元素，要继续结算，右侧的小值是不存在，为-1
while (!stack.isEmpty()) {
int curIndex = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[curIndex][0] = leftLessIndex;
// 右侧的小值是-1
res[curIndex][1] = -1;
}
return res;
}
2.1.3 支持重复值的数组单调栈的应用方法
- 支持重复值的数组单调栈的应用方法。
- 该方法对没有重复值的也是可以直接使用的。
- 思路：
- 如果数组中存在重复的值，但是题目要求是要小于当前值的值，所以重复的值不能直接放到栈中，如果重复的值放到栈中，结算的时候就会将重复值算为一侧的较小值，这样是不满足题目要求的。
- 但是重复的值也不能不入栈，如果重复的值不入栈，那重复的那个位置就会忽略掉，没办法求出那个位置的两侧较小的值。
- 所以我们在入栈的时候，要在栈中保存一个数组，将值相等的下标合并到一个数组中，这样出栈结算的时候，就能结算所有的下标，也不会出现相同的值。
- 通过合并所有相同值的下标保存在栈中的方法，就可以将数组转为没有相同值的方式来处理了。
- 总结：
- 到底栈中放不放重复的值，是根据题目来定的，这个题目中不能放重复的值，也不能忽略重复的值，但是有的题目可以忽略，这是根据具体题目来决定的。
/**
* 支持重复值的数组单调栈的应用方法。
* 该方法对没有重复值的也是可以直接使用的。
* 思路：
* 如果数组中存在重复的值，但是题目要求是要小于当前值的值，所以重复的值不能直接放到栈中，如果重复的值放到栈中，结算的时候就会将重复值算为一侧的较小值，这样是不满足题目要求的。
* 但是重复的值也不能不入栈，如果重复的值不入栈，那重复的那个位置就会忽略掉，没办法求出那个位置的两侧较小的值。
* 所以我们在入栈的时候，要在栈中保存一个数组，将值相等的下标合并到一个数组中，这样出栈结算的时候，就能结算所有的下标，也不会出现相同的值。
* 通过合并所有相同值的下标保存在栈中的方法，就可以将数组转为没有相同值的方式来处理了。
* <br>
* 总结：
* 到底栈中放不放重复的值，是根据题目来定的，这个题目中不能放重复的值，也不能忽略重复的值，但是有的题目可以忽略，这是根据具体题目来决定的。
*/
public static int[][] getNearLess(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0][2];
}
int[][] res = new int[arr.length][2];
// 栈中存放一个列表
Stack<List<Integer>> stack = new Stack<>();
// 循环所有下标
for (int i = 0; i < arr.length; i++) {
// 将大于当前值的出栈
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
// 弹出要结算的下标集合
List<Integer> curIndexes = stack.pop();
// 其左侧的第一个就是栈中下标集合的最后一个
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
// 计算所有的集合
for (Integer curIndex : curIndexes) {
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = i;
}
}
// 当前的下标入栈，先要判断栈顶是不是有相同的值，有的话就加入，没有就新建一个
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(i);
} else {
List<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
// 结算栈中剩余的值
while (!stack.isEmpty()) {
List<Integer> curIndexes = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer curIndex : curIndexes) {
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = -1;
}
}
return res;
}
整体代码和测试如下：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 题目一：求数组的每个位置左右两侧离其最近且比其小的数
*/
public class Q1_NearMinValue {
/**
* 暴力方法实现的对数器
* 思路：
* 到每一个位置，到左右两侧遍历去获取比它小的值。
*/
public static int[][] comparator(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0][2];
}
int[][] res = new int[arr.length][2];
// 循环每个位置
for (int i = 0; i < arr.length; i++) {
// 找到左侧最小值
int leftLessIndex = -1;
// 从i左侧第一个开始
int cur = i - 1;
while (cur >= 0) {
// 找到第一个小的，就退出循环
if (arr[cur] < arr[i]) {
leftLessIndex = cur;
break;
}
cur--;
}
// 找到右侧最小值
int rightLessIndex = -1;
// 从i右侧第一个开始
cur = i + 1;
while (cur < arr.length) {
// 找到第一个小的，就退出循环
if (arr[cur] < arr[i]) {
rightLessIndex = cur;
break;
}
cur++;
}
res[i][0] = leftLessIndex;
res[i][1] = rightLessIndex;
}
return res;
}
/**
* 没有重复值的数组单调栈的应用方法。
* 思路：
* 对于没有重复值的数组来说，应用单调栈的方法能很快找出其左右两侧最近的最小值。
* 我们准备一个单调递增的栈，依次将元素加入到栈中，在加入一个元素的时候，如果栈顶元素大于当前的元素，就将其出栈，此时右侧的最小值就是让它出栈的值，
* 左侧的最小值就是此时栈中的栈顶元素。如果此时栈中已经没有元素了，说明没有左侧的最小值。
* 当所有元素都循环一遍以后，栈中还有值，要将栈中的值依次出栈，此时右侧没有最小值，左侧最小值依然是当前值出栈以后的栈顶元素，如果栈中没有，说明也没有左侧最小值。
*/
public static int[][] getNearLessNoRepeat(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0][2];
}
int[][] res = new int[arr.length][2];
Stack<Integer> stack = new Stack<>();
// 将所有元素依次入栈,栈中保存的是下标，不是真正的值
for (int i = 0; i < arr.length; i++) {
// 将栈中大于目前值的出栈，并结算出栈的下标的左右最小值，填充到结果数组中
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
// 要结算的下标是第一个出栈的值
int curIndex = stack.pop();
// 左侧小值是此时栈顶元素，如果没有就是没有左侧最小值
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[curIndex][0] = leftLessIndex;
// 右侧的小值就是让其出栈的值
res[curIndex][1] = i;
}
// 所有大于当前值的都出栈结算后，当前的下标要入栈
stack.push(i);
}
// 栈中还有元素，要继续结算，右侧的小值是不存在，为-1
while (!stack.isEmpty()) {
int curIndex = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[curIndex][0] = leftLessIndex;
// 右侧的小值是-1
res[curIndex][1] = -1;
}
return res;
}
/**
* 支持重复值的数组单调栈的应用方法。
* 该方法对没有重复值的也是可以直接使用的。
* 思路：
* 如果数组中存在重复的值，但是题目要求是要小于当前值的值，所以重复的值不能直接放到栈中，如果重复的值放到栈中，结算的时候就会将重复值算为一侧的较小值，这样是不满足题目要求的。
* 但是重复的值也不能不入栈，如果重复的值不入栈，那重复的那个位置就会忽略掉，没办法求出那个位置的两侧较小的值。
* 所以我们在入栈的时候，要在栈中保存一个数组，将值相等的下标合并到一个数组中，这样出栈结算的时候，就能结算所有的下标，也不会出现相同的值。
* 通过合并所有相同值的下标保存在栈中的方法，就可以将数组转为没有相同值的方式来处理了。
* <br>
* 总结：
* 到底栈中放不放重复的值，是根据题目来定的，这个题目中不能放重复的值，也不能忽略重复的值，但是有的题目可以忽略，这是根据具体题目来决定的。
*/
public static int[][] getNearLess(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0][2];
}
int[][] res = new int[arr.length][2];
// 栈中存放一个列表
Stack<List<Integer>> stack = new Stack<>();
// 循环所有下标
for (int i = 0; i < arr.length; i++) {
// 将大于当前值的出栈
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
// 弹出要结算的下标集合
List<Integer> curIndexes = stack.pop();
// 其左侧的第一个就是栈中下标集合的最后一个
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
// 计算所有的集合
for (Integer curIndex : curIndexes) {
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = i;
}
}
// 当前的下标入栈，先要判断栈顶是不是有相同的值，有的话就加入，没有就新建一个
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(i);
} else {
List<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
// 结算栈中剩余的值
while (!stack.isEmpty()) {
List<Integer> curIndexes = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer curIndex : curIndexes) {
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = -1;
}
}
return res;
}
public static void main(String[] args) {
int size = 20;
int max = 20;
int testTimes = 2000000;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
int[] arr1 = getRandomArrayNoRepeat(size);
int[] arr2 = getRandomArray(size, max);
if (!isEqual(getNearLessNoRepeat(arr1), comparator(arr1))) {
System.out.println("没有重复值错误!");
printArray(arr1);
break;
}
if (!isEqual(getNearLess(arr2), comparator(arr2))) {
System.out.println("有重复值错误!");
printArray(arr2);
break;
}
}
System.out.println("测试结束");
}
// for test
public static int[] getRandomArrayNoRepeat(int size) {
int[] arr = new int[(int) (Math.random() * size) + 1];
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
for (int i = 0; i < arr.length; i++) {
int swapIndex = (int) (Math.random() * arr.length);
int tmp = arr[swapIndex];
arr[swapIndex] = arr[i];
arr[i] = tmp;
}
return arr;
}
// for test
public static int[] getRandomArray(int size, int max) {
int[] arr = new int[(int) (Math.random() * size) + 1];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
}
return arr;
}
// for test
public static boolean isEqual(int[][] res1, int[][] res2) {
if (res1.length != res2.length) {
return false;
}
for (int i = 0; i < res1.length; i++) {
if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
2.2、题目二：单调栈结构(牛客网)
- 题目二：单调栈结构(牛客网)
- 测试链接：https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb
- 提交如下的代码，并把主类名改成"Main",上面的import也要加上
main函数如下：
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
int n = (int) in.nval;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
in.nextToken();
arr[i] = (int) in.nval;
}
//int[][] ans = getNearLessWithStack(arr);
int[][] ans = getNearLessWithArray(arr);
for (int i = 0; i < n; i++) {
out.println(ans[i][0] + " " + ans[i][1]);
}
out.flush();
}
}
2.2.1 利用系统提供的栈的方式求解
/**
* 利用系统提供的栈的方式求解
* 思路：
* 和题目一求解包含重复值数组的方式一样
*/
private static int[][] getNearLessWithStack(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0][2];
}
int[][] res = new int[arr.length][2];
// 栈中存放一个列表
Stack<List<Integer>> stack = new Stack<>();
// 循环所有下标
for (int i = 0; i < arr.length; i++) {
// 将大于当前值的出栈
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
// 弹出要结算的下标集合
List<Integer> curIndexes = stack.pop();
// 其左侧的第一个就是栈中下标集合的最后一个
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
// 计算所有的集合
for (Integer curIndex : curIndexes) {
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = i;
}
}
// 当前的下标入栈，先要判断栈顶是不是有相同的值，有的话就加入，没有就新建一个
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(i);
} else {
List<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
// 结算栈中剩余的值
while (!stack.isEmpty()) {
List<Integer> curIndexes = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer curIndex : curIndexes) {
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = -1;
}
}
return res;
}
2.2.2 使用数组模拟栈的方式来求解
- 使用数组模拟栈的方式来求解
- 思路：
- 我们可以用一个数组来模拟一个栈，使用一个下标变量stackIndex，表示当前栈顶元素的位置，为-1时表示栈为空，这样可以提高执行的效率。
- 本题目中有重复值，如果用一个数组来表示，用上面的方法数组中可以放一个list(这种方法就不演示了)，当然也可以用两个数组来模拟。
- 在题目一中我们分析过，如果将相等的值也放到栈中，那么左侧拿到的就是一个相等的值，而不是小于的值。
- 我们可以用两个站，stack1连相等值的位置也放，stack2只放不相等值的最后一个位置，
- 比如 : arr = { 3, 3, 3, 4, 4, 6, 6, 6}
- ---------位置 0 1 2 3 4 5 6 7
- 如果位置依次压栈，
- stack1中的记录是（位置） : 0 1 2 3 4 5 6 7
- stack2中的记录是（位置） : 2 4 7
- 因为stack2中存放的是相等值的最右侧的位置，那么此时如果弹出一个stack1的栈顶元素，其左侧的小值就是stack2的栈顶下标-1的位置所对应的值。
- 因为当前stack2中栈顶元素和要弹出的stack1中的相等值的元素的最右侧的下标，
- 当每次从stack1中弹出一个元素的时候，要判断当前的值和stack1中栈顶元素的值是否不同了，如果不同，将stack2栈顶元素也弹出。
- 总结：
- 这种方式比较复杂，两个下标很容易出错，平时练习的时候可以试试，正式还是直接用系统提供的stack或者数组中存放list比较合适
/**
* 使用数组模拟栈的方式来求解
* 思路：
* 我们可以用一个数组来模拟一个栈，使用一个下标变量stackIndex，表示当前栈顶元素的位置，为-1时表示栈为空，这样可以提高执行的效率。
* 本题目中有重复值，如果用一个数组来表示，用上面的方法数组中可以放一个list(这种方法就不演示了)，当然也可以用两个数组来模拟。
* 在题目一中我们分析过，如果将相等的值也放到栈中，那么左侧拿到的就是一个相等的值，而不是小于的值。
* 我们可以用两个站，stack1连相等值的位置也放，stack2只放不相等值的最后一个位置，
* 比如 : arr = { 3, 3, 3, 4, 4, 6, 6, 6}
* ---------位置 0 1 2 3 4 5 6 7
* 如果位置依次压栈，
* stack1中的记录是（位置） : 0 1 2 3 4 5 6 7
* stack2中的记录是（位置） : 2 4 7
* 因为stack2中存放的是相等值的最右侧的位置，那么此时如果弹出一个stack1的栈顶元素，其左侧的小值就是stack2的栈顶下标-1的位置所对应的值。
* 因为当前stack2中栈顶元素和要弹出的stack1中的相等值的元素的最右侧的下标，
* 当每次从stack1中弹出一个元素的时候，要判断当前的值和stack1中栈顶元素的值是否不同了，如果不同，将stack2栈顶元素也弹出。
* <br>
* 总结：
* 这种方式比较复杂，两个下标很容易出错，平时练习的时候可以试试，正式还是直接用系统提供的stack或者数组中存放list比较合适
*/
private static int[][] getNearLessWithArray(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0][2];
}
int n = arr.length;
int[][] res = new int[n][2];
// stack1的栈顶下标和数组
int stackIndex1 = -1;
int[] stack1 = new int[n];
// stack2的栈顶下标和数组
int stackIndex2 = -1;
int[] stack2 = new int[n];
// 循环数组元素
for (int i = 0; i < n; i++) {
// stack1中有大于当前元素的值，需要结算
while (stackIndex1 > -1 && arr[stack1[stackIndex1]] > arr[i]) {
// 当前index就是stack1弹出的栈顶元素
int curIndex = stack1[stackIndex1--];
// 其左侧就是stack2次栈顶元素的值
int leftLessIndex = stackIndex2 < 1 ? -1 : stack2[stackIndex2 - 1];
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = i;
// stack1弹出元素以后，如果此时的栈顶元素和当前值不同，代表弹出的值已经和stack1中没有重复值了，stack2要弹出一个元素
if (stackIndex1 == -1 || arr[stack1[stackIndex1]] != arr[curIndex]) {
stackIndex2--;
}
}
// 对于stack2，如果当前值和stack1的栈顶元素相同，则更新为当前下标，否则加入
if (stackIndex1 != -1 && arr[stack1[stackIndex1]] == arr[i]) {
stack2[stackIndex2] = i;
} else {
stack2[++stackIndex2] = i;
}
// stack1直接加入当前值
stack1[++stackIndex1] = i;
}
// 栈中还有值，继续弹出
while (stackIndex1 > -1) {
// 当前index就是stack1弹出的栈顶元素
int curIndex = stack1[stackIndex1--];
// 其左侧就是stack2次栈顶元素的值
int leftLessIndex = stackIndex2 < 1 ? -1 : stack2[stackIndex2 - 1];
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = -1;
// stack1弹出元素以后，如果此时的栈顶元素和当前值不同，代表弹出的值已经和stack1中没有重复值了，stack2要弹出一个元素
if (stackIndex1 == -1 || arr[stack1[stackIndex1]] != arr[curIndex]) {
stackIndex2--;
}
}
return res;
}
整体代码和测试如下：
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 题目二：单调栈结构(牛客网)
* 测试链接：https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb
* 提交如下的代码，并把主类名改成"Main",上面的import也要加上
*/
public class Q2_NearMinValueNowcoder {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
int n = (int) in.nval;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
in.nextToken();
arr[i] = (int) in.nval;
}
//int[][] ans = getNearLessWithStack(arr);
int[][] ans = getNearLessWithArray(arr);
for (int i = 0; i < n; i++) {
out.println(ans[i][0] + " " + ans[i][1]);
}
out.flush();
}
}
/**
* 利用系统提供的栈的方式求解
* 思路：
* 和题目一求解包含重复值数组的方式一样
*/
private static int[][] getNearLessWithStack(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0][2];
}
int[][] res = new int[arr.length][2];
// 栈中存放一个列表
Stack<List<Integer>> stack = new Stack<>();
// 循环所有下标
for (int i = 0; i < arr.length; i++) {
// 将大于当前值的出栈
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
// 弹出要结算的下标集合
List<Integer> curIndexes = stack.pop();
// 其左侧的第一个就是栈中下标集合的最后一个
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
// 计算所有的集合
for (Integer curIndex : curIndexes) {
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = i;
}
}
// 当前的下标入栈，先要判断栈顶是不是有相同的值，有的话就加入，没有就新建一个
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(i);
} else {
List<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
// 结算栈中剩余的值
while (!stack.isEmpty()) {
List<Integer> curIndexes = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer curIndex : curIndexes) {
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = -1;
}
}
return res;
}
/**
* 使用数组模拟栈的方式来求解
* 思路：
* 我们可以用一个数组来模拟一个栈，使用一个下标变量stackIndex，表示当前栈顶元素的位置，为-1时表示栈为空，这样可以提高执行的效率。
* 本题目中有重复值，如果用一个数组来表示，用上面的方法数组中可以放一个list(这种方法就不演示了)，当然也可以用两个数组来模拟。
* 在题目一中我们分析过，如果将相等的值也放到栈中，那么左侧拿到的就是一个相等的值，而不是小于的值。
* 我们可以用两个站，stack1连相等值的位置也放，stack2只放不相等值的最后一个位置，
* 比如 : arr = { 3, 3, 3, 4, 4, 6, 6, 6}
* ---------位置 0 1 2 3 4 5 6 7
* 如果位置依次压栈，
* stack1中的记录是（位置） : 0 1 2 3 4 5 6 7
* stack2中的记录是（位置） : 2 4 7
* 因为stack2中存放的是相等值的最右侧的位置，那么此时如果弹出一个stack1的栈顶元素，其左侧的小值就是stack2的栈顶下标-1的位置所对应的值。
* 因为当前stack2中栈顶元素和要弹出的stack1中的相等值的元素的最右侧的下标，
* 当每次从stack1中弹出一个元素的时候，要判断当前的值和stack1中栈顶元素的值是否不同了，如果不同，将stack2栈顶元素也弹出。
* <br>
* 总结：
* 这种方式比较复杂，两个下标很容易出错，平时练习的时候可以试试，正式还是直接用系统提供的stack或者数组中存放list比较合适
*/
private static int[][] getNearLessWithArray(int[] arr) {
if (arr == null || arr.length == 0) {
return new int[0][2];
}
int n = arr.length;
int[][] res = new int[n][2];
// stack1的栈顶下标和数组
int stackIndex1 = -1;
int[] stack1 = new int[n];
// stack2的栈顶下标和数组
int stackIndex2 = -1;
int[] stack2 = new int[n];
// 循环数组元素
for (int i = 0; i < n; i++) {
// stack1中有大于当前元素的值，需要结算
while (stackIndex1 > -1 && arr[stack1[stackIndex1]] > arr[i]) {
// 当前index就是stack1弹出的栈顶元素
int curIndex = stack1[stackIndex1--];
// 其左侧就是stack2次栈顶元素的值
int leftLessIndex = stackIndex2 < 1 ? -1 : stack2[stackIndex2 - 1];
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = i;
// stack1弹出元素以后，如果此时的栈顶元素和当前值不同，代表弹出的值已经和stack1中没有重复值了，stack2要弹出一个元素
if (stackIndex1 == -1 || arr[stack1[stackIndex1]] != arr[curIndex]) {
stackIndex2--;
}
}
// 对于stack2，如果当前值和stack1的栈顶元素相同，则更新为当前下标，否则加入
if (stackIndex1 != -1 && arr[stack1[stackIndex1]] == arr[i]) {
stack2[stackIndex2] = i;
} else {
stack2[++stackIndex2] = i;
}
// stack1直接加入当前值
stack1[++stackIndex1] = i;
}
// 栈中还有值，继续弹出
while (stackIndex1 > -1) {
// 当前index就是stack1弹出的栈顶元素
int curIndex = stack1[stackIndex1--];
// 其左侧就是stack2次栈顶元素的值
int leftLessIndex = stackIndex2 < 1 ? -1 : stack2[stackIndex2 - 1];
res[curIndex][0] = leftLessIndex;
res[curIndex][1] = -1;
// stack1弹出元素以后，如果此时的栈顶元素和当前值不同，代表弹出的值已经和stack1中没有重复值了，stack2要弹出一个元素
if (stackIndex1 == -1 || arr[stack1[stackIndex1]] != arr[curIndex]) {
stackIndex2--;
}
}
return res;
}
}
2.3、题目三：子数组最小乘积的最大值
- 题目三：子数组最小乘积的最大值
- 给定一个只包含正数的数组arr，arr中任何一个子数组sub，
- 一定都可以算出(sub累加和)*(sub中的最小值)是什么，
- 那么所有子数组中，这个值最大是多少？
- 测试链接 : https://leetcode.cn/problems/maximum-subarray-min-product/
- 由于答案可能很大，请你返回答案对10^9 + 7 取余的结果。
2.3.1 暴力方法
- 暴力解法
- 思路：
- 枚举所有子数组，计算子数组的最小乘积，取最大值
- 在每个子数组中，要计算两个值，一个是最小值，一个是累加和，可以遍历一次子数组求出来这两个值。
- 提交时方法名改为：maxSumMinProduct，会超时
/**
* 暴力解法
* 思路：
* 枚举所有子数组，计算子数组的最小乘积，取最大值
* 在每个子数组中，要计算两个值，一个是最小值，一个是累加和，可以遍历一次子数组求出来这两个值。
* 提交时方法名改为：maxSumMinProduct，会超时
*/
public static int maxSumMinProduct1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
long max = Long.MIN_VALUE;
// 循环每个子数组
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
// 计算子数组[i,j]的累加和和最小值
int minNum = arr[i];
int sum = arr[i];
for (int k = i + 1; k <= j; k++) {
sum += arr[k];
minNum = Math.min(minNum, arr[k]);
}
// 求出累加和与最小值的乘积
long res = (long) sum * minNum;
// 取到最大值
max = Math.max(max, res);
}
}
return (int) (max % 1000000007);
}
2.3.2 使用单调栈的解法
- 使用单调栈的解法：
- 思路：
- 题目要求是求出子数组中累加和和最小值的乘积的最大值。
- 我们知道，对于一个子数组，如果最小值是相同的，其最后乘积的最大值就是由累加和决定的，因为都是正数，当然包含的数越多，累加和就越大，
- 所以题目就可以将思路转为：对于以某个值x为最小值的子数组，求出其最大包含的边界，算出累加和，然后在这些乘积里面挑出最大值即可。
- 这样就需要解决两个问题：1、如何确定以某个值为最小值的子数组边界；2、求这个子数组的累加和
- 我们可以分开讨论：
- 1、如何确定以某个值为最小值的子数组边界?
- 这是单调栈擅长解决的问题，单调栈就是可以轻松的找出一个值距离其两侧最近的小于其的值，找出这两个值以后，左右各缩一个位置，就是我们需要的子数组边界。
- 因为题目要求是一个范围的累加和与最小值的乘积，所以当有相等的值的时候，就可以直接将其弹出，对于和i位置相等的值，先弹出代表范围变窄了，
- 但是对于其更右侧的相等的值的位置，其范围就会更广，会包含上当前的范围，所以最终的结果是不变的。
- 对于乘积的最大值是没有影响的。所以也不用担心数组中有重复值的问题。
- 2、求这个子数组的累加和
- 求一个数组上的累加和，我们可以借助累加和数组，累加和数组就是将数组前一个位置的值和当前位置相加，放在当前位置，整个数组的最后一个值，就是所有数组的累加和。
- 此时i位置的值就是[0,i]的累加和，j位置的值就是[0,j]位置的累加和，此时[i,j]的累加和就是[0,j]-[0,i-1]的值,要注意边界是否包含i位置。
- 提交时方法名改为：maxSumMinProduct
/**
* 使用单调栈的解法：
* 思路：
* 题目要求是求出子数组中累加和和最小值的乘积的最大值。
* 我们知道，对于一个子数组，如果最小值是相同的，其最后乘积的最大值就是由累加和决定的，因为都是正数，当然包含的数越多，累加和就越大，
* 所以题目就可以将思路转为：对于以某个值x为最小值的子数组，求出其最大包含的边界，算出累加和，然后在这些乘积里面挑出最大值即可。
* 这样就需要解决两个问题：1、如何确定以某个值为最小值的子数组边界；2、求这个子数组的累加和
* 我们可以分开讨论：
* <br>
* 1、如何确定以某个值为最小值的子数组边界?
* 这是单调栈擅长解决的问题，单调栈就是可以轻松的找出一个值距离其两侧最近的小于其的值，找出这两个值以后，左右各缩一个位置，就是我们需要的子数组边界。
* 因为题目要求是一个范围的累加和与最小值的乘积，所以当有相等的值的时候，就可以直接将其弹出，对于和i位置相等的值，先弹出代表范围变窄了，
* 但是对于其更右侧的相等的值的位置，其范围就会更广，会包含上当前的范围，所以最终的结果是不变的。
* 对于乘积的最大值是没有影响的。所以也不用担心数组中有重复值的问题。
* <br>
* 2、求这个子数组的累加和
* 求一个数组上的累加和，我们可以借助累加和数组，累加和数组就是将数组前一个位置的值和当前位置相加，放在当前位置，整个数组的最后一个值，就是所有数组的累加和。
* 此时i位置的值就是[0,i]的累加和，j位置的值就是[0,j]位置的累加和，此时[i,j]的累加和就是[0,j]-[0,i-1]的值,要注意边界是否包含i位置。
* <br>
* 提交时方法名改为：maxSumMinProduct
*/
public static int maxSumMinProduct2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int n = arr.length;
// 填充累加和数组
long[] sums = new long[n];
sums[0] = arr[0];
for (int i = 1; i < n; i++) {
sums[i] = sums[i - 1] + arr[i];
}
long max = Long.MIN_VALUE;
// 利用单调栈求解，栈中放的是下标
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
// 将栈中大于等于的弹出，然后求解
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
int curIndex = stack.pop();
// 对于累加和，如果没有左侧小值，则代表从0开始，直接到当前位置，如果有，要用当前位置减去左边界的前一个位置
// 注意，此时的有效位置是[stack.peer() + 1,i -1],i和stack.peek()的位置都是不能包含的，因为这两个位置是比它小的值，最小值变了。
long sum = stack.isEmpty() ? sums[i - 1] : sums[i - 1] - sums[stack.peek()];
max = Math.max(max, sum * arr[curIndex]);
}
stack.push(i);
}
// 求出其他的栈中的位置
while (!stack.isEmpty()) {
int curIndex = stack.pop();
long sum = stack.isEmpty() ? sums[n - 1] : sums[n - 1] - sums[stack.peek()];
max = Math.max(max, sum * arr[curIndex]);
}
return (int) (max % 1000000007);
}
2.3.3 自定义数组单调栈的解法
- 自定义数组单调栈的解法：
- 思路：
- 方法和上面是一样的，用数字自定义栈来代替系统栈，提升效率
/**
* 自定义数组单调栈的解法：
* 思路：
* 方法和上面是一样的，用数字自定义栈来代替系统栈，提升效率
*/
public static int maxSumMinProduct(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int n = arr.length;
// 填充累加和数组
long[] sums = new long[n];
sums[0] = arr[0];
for (int i = 1; i < n; i++) {
sums[i] = sums[i - 1] + arr[i];
}
long max = Long.MIN_VALUE;
// 利用单调栈求解，栈中放的是下标
int stackIndex = -1;
int[] stack = new int[n];
for (int i = 0; i < n; i++) {
while (stackIndex > -1 && arr[stack[stackIndex]] >= arr[i]) {
int curIndex = stack[stackIndex--];
// 对于累加和，如果没有左侧小值，则代表从0开始，直接到当前位置，如果有，要用当前位置减去左边界的前一个位置
// 注意，此时的有效位置是[stack.peer() + 1,i -1],i和stack.peek()的位置都是不能包含的，因为这两个位置是比它小的值，最小值变了。
long sum = stackIndex == -1 ? sums[i - 1] : sums[i - 1] - sums[stack[stackIndex]];
max = Math.max(max, sum * arr[curIndex]);
}
stack[++stackIndex] = i;
}
// 求出其他的栈中的位置
while (stackIndex > -1) {
int curIndex = stack[stackIndex--];
long sum = stackIndex == -1 ? sums[n - 1] : sums[n - 1] - sums[stack[stackIndex]];
max = Math.max(max, sum * arr[curIndex]);
}
return (int) (max % 1000000007);
}
整体代码和测试如下：
/**
* 题目三：子数组最小乘积的最大值
* 给定一个只包含正数的数组arr，arr中任何一个子数组sub，
* 一定都可以算出(sub累加和)*(sub中的最小值)是什么，
* 那么所有子数组中，这个值最大是多少？
* 测试链接 : https://leetcode.cn/problems/maximum-subarray-min-product/
* 由于答案可能很大，请你返回答案对10^9 + 7 取余的结果。
*/
public class Q3_MaxSubMinProduct {
/**
* 暴力解法
* 思路：
* 枚举所有子数组，计算子数组的最小乘积，取最大值
* 在每个子数组中，要计算两个值，一个是最小值，一个是累加和，可以遍历一次子数组求出来这两个值。
* 提交时方法名改为：maxSumMinProduct，会超时
*/
public static int maxSumMinProduct1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
long max = Long.MIN_VALUE;
// 循环每个子数组
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
// 计算子数组[i,j]的累加和和最小值
int minNum = arr[i];
int sum = arr[i];
for (int k = i + 1; k <= j; k++) {
sum += arr[k];
minNum = Math.min(minNum, arr[k]);
}
// 求出累加和与最小值的乘积
long res = (long) sum * minNum;
// 取到最大值
max = Math.max(max, res);
}
}
return (int) (max % 1000000007);
}
/**
* 使用单调栈的解法：
* 思路：
* 题目要求是求出子数组中累加和和最小值的乘积的最大值。
* 我们知道，对于一个子数组，如果最小值是相同的，其最后乘积的最大值就是由累加和决定的，因为都是正数，当然包含的数越多，累加和就越大，
* 所以题目就可以将思路转为：对于以某个值x为最小值的子数组，求出其最大包含的边界，算出累加和，然后在这些乘积里面挑出最大值即可。
* 这样就需要解决两个问题：1、如何确定以某个值为最小值的子数组边界；2、求这个子数组的累加和
* 我们可以分开讨论：
* <br>
* 1、如何确定以某个值为最小值的子数组边界?
* 这是单调栈擅长解决的问题，单调栈就是可以轻松的找出一个值距离其两侧最近的小于其的值，找出这两个值以后，左右各缩一个位置，就是我们需要的子数组边界。
* 因为题目要求是一个范围的累加和与最小值的乘积，所以当有相等的值的时候，就可以直接将其弹出，对于和i位置相等的值，先弹出代表范围变窄了，
* 但是对于其更右侧的相等的值的位置，其范围就会更广，会包含上当前的范围，所以最终的结果是不变的。
* 对于乘积的最大值是没有影响的。所以也不用担心数组中有重复值的问题。
* <br>
* 2、求这个子数组的累加和
* 求一个数组上的累加和，我们可以借助累加和数组，累加和数组就是将数组前一个位置的值和当前位置相加，放在当前位置，整个数组的最后一个值，就是所有数组的累加和。
* 此时i位置的值就是[0,i]的累加和，j位置的值就是[0,j]位置的累加和，此时[i,j]的累加和就是[0,j]-[0,i-1]的值,要注意边界是否包含i位置。
* <br>
* 提交时方法名改为：maxSumMinProduct
*/
public static int maxSumMinProduct2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int n = arr.length;
// 填充累加和数组
long[] sums = new long[n];
sums[0] = arr[0];
for (int i = 1; i < n; i++) {
sums[i] = sums[i - 1] + arr[i];
}
long max = Long.MIN_VALUE;
// 利用单调栈求解，栈中放的是下标
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
// 将栈中大于等于的弹出，然后求解
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
int curIndex = stack.pop();
// 对于累加和，如果没有左侧小值，则代表从0开始，直接到当前位置，如果有，要用当前位置减去左边界的前一个位置
// 注意，此时的有效位置是[stack.peer() + 1,i -1],i和stack.peek()的位置都是不能包含的，因为这两个位置是比它小的值，最小值变了。
long sum = stack.isEmpty() ? sums[i - 1] : sums[i - 1] - sums[stack.peek()];
max = Math.max(max, sum * arr[curIndex]);
}
stack.push(i);
}
// 求出其他的栈中的位置
while (!stack.isEmpty()) {
int curIndex = stack.pop();
long sum = stack.isEmpty() ? sums[n - 1] : sums[n - 1] - sums[stack.peek()];
max = Math.max(max, sum * arr[curIndex]);
}
return (int) (max % 1000000007);
}
/**
* 自定义数组单调栈的解法：
* 思路：
* 方法和上面是一样的，用数字自定义栈来代替系统栈，提升效率
*/
public static int maxSumMinProduct(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int n = arr.length;
// 填充累加和数组
long[] sums = new long[n];
sums[0] = arr[0];
for (int i = 1; i < n; i++) {
sums[i] = sums[i - 1] + arr[i];
}
long max = Long.MIN_VALUE;
// 利用单调栈求解，栈中放的是下标
int stackIndex = -1;
int[] stack = new int[n];
for (int i = 0; i < n; i++) {
while (stackIndex > -1 && arr[stack[stackIndex]] >= arr[i]) {
int curIndex = stack[stackIndex--];
// 对于累加和，如果没有左侧小值，则代表从0开始，直接到当前位置，如果有，要用当前位置减去左边界的前一个位置
// 注意，此时的有效位置是[stack.peer() + 1,i -1],i和stack.peek()的位置都是不能包含的，因为这两个位置是比它小的值，最小值变了。
long sum = stackIndex == -1 ? sums[i - 1] : sums[i - 1] - sums[stack[stackIndex]];
max = Math.max(max, sum * arr[curIndex]);
}
stack[++stackIndex] = i;
}
// 求出其他的栈中的位置
while (stackIndex > -1) {
int curIndex = stack[stackIndex--];
long sum = stackIndex == -1 ? sums[n - 1] : sums[n - 1] - sums[stack[stackIndex]];
max = Math.max(max, sum * arr[curIndex]);
}
return (int) (max % 1000000007);
}
public static void main(String[] args) {
int testTimes = 2000000;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
int[] arr = gerenareRondomArray();
int ans1 = maxSumMinProduct1(arr);
int ans2 = maxSumMinProduct2(arr);
int ans3 = maxSumMinProduct(arr);
if (ans1 != ans2 || ans1 != ans3) {
System.out.println("错误!");
printArray(arr);
System.out.printf("ans1 = %d, ans2 = %d, ans3 = %d\n", ans1, ans2, ans3);
break;
}
}
System.out.println("测试结束");
}
public static int[] gerenareRondomArray() {
int[] arr = new int[(int) (Math.random() * 20) + 10];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 101);
}
return arr;
}
// for test
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
2.4、题目四：柱状图中最大的矩形
- 题目四：柱状图中最大的矩形
- 给定一个非负的数组arr，代表直方图，返回直方图最大的长方形的面积
- 测试链接：https://leetcode.cn/problems/largest-rectangle-in-histogram
2.4.1 利用系统栈的解法
- 利用系统栈的解法
- 思路：
- 本题求的是形成的长方形的最大面积，和题目三的思路是一样的，确定了一个数为最小值的长方形，只需要计算出长方形的底的长度就可以了。
- 分别以每个数作为最小值，利用单调栈的方法求出这个数组的左右边界，即可以求出以这个数为最小值的长方形的面积。
- 比如利用单调栈求出来的两个最近的小于的边界为left和right，那么以这个数为最小值的长方形的面积就是(right - left - 1) * height[i]
- 因为球的是最大的面积，所以在值相同的时候，前面结算了，后面直接入栈，后面的跨度会更大，不影响最后的结果
- 提交时方法名改为：largestRectangleArea
/**
* 利用系统栈的解法
* 思路：
* 本题求的是形成的长方形的最大面积，和题目三的思路是一样的，确定了一个数为最小值的长方形，只需要计算出长方形的底的长度就可以了。
* 分别以每个数作为最小值，利用单调栈的方法求出这个数组的左右边界，即可以求出以这个数为最小值的长方形的面积。
* 比如利用单调栈求出来的两个最近的小于的边界为left和right，那么以这个数为最小值的长方形的面积就是(right - left - 1) * height[i]
* 因为球的是最大的面积，所以在值相同的时候，前面结算了，后面直接入栈，后面的跨度会更大，不影响最后的结果
* <br>
* 提交时方法名改为：largestRectangleArea
*/
public int largestRectangleArea1(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int maxArea = 0;
Stack<Integer> stack = new Stack<>();
// 循环所有下标
for (int i = 0; i < heights.length; i++) {
// 将大于当前值的出栈
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
// 弹出要结算的下标
int curIndex = stack.pop();
// 其左侧的第一个就是栈中下标集合的最后一个
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
// 计算当前面积
int curArea = (i - leftLessIndex - 1) * heights[curIndex];
maxArea = Math.max(maxArea, curArea);
}
// 当前的下标入栈
stack.push(i);
}
// 结算栈中剩余的值
while (!stack.isEmpty()) {
int curIndex = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
int curArea = (heights.length - leftLessIndex - 1) * heights[curIndex];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
2.4.2 自定义数组单调栈的解法
- 自定义数组单调栈的解法
- 思路:
- 和利用系统栈的方式求解是一样的，只是利用数组模拟栈的方式来求解，提升单位时间的执行效率
/**
* 自定义数组单调栈的解法
* 思路:
* 和利用系统栈的方式求解是一样的，只是利用数组模拟栈的方式来求解，提升单位时间的执行效率
*/
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int maxArea = 0;
int n = heights.length;
// 用数组模拟栈
int stackIndex = -1;
int[] stack = new int[n];
// 循环所有下标
for (int i = 0; i < n; i++) {
// 将大于当前值的出栈
while (stackIndex > -1 && heights[stack[stackIndex]] >= heights[i]) {
// 弹出要结算的下标
int curIndex = stack[stackIndex--];
// 其左侧的第一个就是栈中下标集合的最后一个
int leftLessIndex = stackIndex == -1 ? -1 : stack[stackIndex];
// 计算当前面积
int curArea = (i - leftLessIndex - 1) * heights[curIndex];
maxArea = Math.max(maxArea, curArea);
}
// 当前的下标入栈
stack[++stackIndex] = i;
}
// 结算栈中剩余的值
while (stackIndex > -1) {
int curIndex = stack[stackIndex--];
int leftLessIndex = stackIndex == -1 ? -1 : stack[stackIndex];
int curArea = (n - leftLessIndex - 1) * heights[curIndex];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
整体代码和测试：
import java.util.Stack;
/**
* 题目四：柱状图中最大的矩形
* 给定一个非负的数组arr，代表直方图，返回直方图最大的长方形的面积
* 测试链接：https://leetcode.cn/problems/largest-rectangle-in-histogram
*/
public class Q4_LargestRectangleInHistogram {
/**
* 利用系统栈的解法
* 思路：
* 本题求的是形成的长方形的最大面积，和题目三的思路是一样的，确定了一个数为最小值的长方形，只需要计算出长方形的底的长度就可以了。
* 分别以每个数作为最小值，利用单调栈的方法求出这个数组的左右边界，即可以求出以这个数为最小值的长方形的面积。
* 比如利用单调栈求出来的两个最近的小于的边界为left和right，那么以这个数为最小值的长方形的面积就是(right - left - 1) * height[i]
* 因为球的是最大的面积，所以在值相同的时候，前面结算了，后面直接入栈，后面的跨度会更大，不影响最后的结果
* <br>
* 提交时方法名改为：largestRectangleArea
*/
public int largestRectangleArea1(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int maxArea = 0;
Stack<Integer> stack = new Stack<>();
// 循环所有下标
for (int i = 0; i < heights.length; i++) {
// 将大于当前值的出栈
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
// 弹出要结算的下标
int curIndex = stack.pop();
// 其左侧的第一个就是栈中下标集合的最后一个
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
// 计算当前面积
int curArea = (i - leftLessIndex - 1) * heights[curIndex];
maxArea = Math.max(maxArea, curArea);
}
// 当前的下标入栈
stack.push(i);
}
// 结算栈中剩余的值
while (!stack.isEmpty()) {
int curIndex = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
int curArea = (heights.length - leftLessIndex - 1) * heights[curIndex];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
/**
* 自定义数组单调栈的解法
* 思路:
* 和利用系统栈的方式求解是一样的，只是利用数组模拟栈的方式来求解，提升单位时间的执行效率
*/
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int maxArea = 0;
int n = heights.length;
// 用数组模拟栈
int stackIndex = -1;
int[] stack = new int[n];
// 循环所有下标
for (int i = 0; i < n; i++) {
// 将大于当前值的出栈
while (stackIndex > -1 && heights[stack[stackIndex]] >= heights[i]) {
// 弹出要结算的下标
int curIndex = stack[stackIndex--];
// 其左侧的第一个就是栈中下标集合的最后一个
int leftLessIndex = stackIndex == -1 ? -1 : stack[stackIndex];
// 计算当前面积
int curArea = (i - leftLessIndex - 1) * heights[curIndex];
maxArea = Math.max(maxArea, curArea);
}
// 当前的下标入栈
stack[++stackIndex] = i;
}
// 结算栈中剩余的值
while (stackIndex > -1) {
int curIndex = stack[stackIndex--];
int leftLessIndex = stackIndex == -1 ? -1 : stack[stackIndex];
int curArea = (n - leftLessIndex - 1) * heights[curIndex];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
}
2.5、题目五：最大矩形
- 题目五：最大矩形
- 给定一个二维数组matrix，其中的值不是0就是1，
- 返回全部由1组成的最大子矩形，内部有多少个1
- 测试链接：https://leetcode.cn/problems/maximal-rectangle/
2.5.1 压缩数组+单调栈的解法
- 压缩数组+单调栈的解法
- 思路：
-
- 先将二维数组压缩成一个一维直方图数组height
-
- 然后使用单调栈的方法计算直方图数组height的最大矩形面积
-
- 循环每一行，找到最大的矩形面积
- 循环每一行，找到最大的矩形面积
-
- 压缩数组的思想和方法：
- 如果我们把一个二维数组从行号0开始，到行号i看成是从上到下的层。
- 那么我们就可以从第0行开始，一行一行往下填充一个一维数组，这个一维的数组被称为直方图数组。
- 直方图数组height的意义是，必须以当前行i为底的直方图的大小。其每个元素的高度值代表了第0行到第i行的该位置上连续的1的数量。
- 当我们将每一行转为直方图数组height的时候，就可以单独求出这一行的最大矩形的面积，和题目四的一样。
- 我们从第0行开始，直到数组的最后一行，求每一行的直方图数组中的最大矩形的面积，累计出来的最大值，就是题目要求的最大矩形的面积。
- 压缩数组的求法：
- 1、第0行的压缩数组和原数组第0行是一样的
- 2、从第1行开始，如果记当前行为i，原数组为arr，当前压缩位置为j，则压缩数组height[j]位置的值如下：
- 2.1、如果arr[i][j] == 0,则压缩数组当前位置的值为0，即height[j] = 0
- 2.2、如果arr[i][j] == 1,则压缩数组当前位置的值为当前的值加一，即height[j] = height[j] + 1
- 通过压缩数组的求法，可以直观的看出压缩数组每个位置的值代表了前面连续的1的个数。
/**
* 题目五：最大矩形
* 给定一个二维数组matrix，其中的值不是0就是1，
* 返回全部由1组成的最大子矩形，内部有多少个1
* 测试链接：https://leetcode.cn/problems/maximal-rectangle/
*/
public class Q5_MaximalRectangle {
/**
* 压缩数组+单调栈的解法
* 思路：
* 1. 先将二维数组压缩成一个一维直方图数组height
* 2. 然后使用单调栈的方法计算直方图数组height的最大矩形面积
* 3. 循环每一行，找到最大的矩形面积
* <br>
* 压缩数组的思想和方法：
* 如果我们把一个二维数组从行号0开始，到行号i看成是从上到下的层。
* 那么我们就可以从第0行开始，一行一行往下填充一个一维数组，这个一维的数组被称为直方图数组。
* 直方图数组height的意义是，必须以当前行i为底的直方图的大小。其每个元素的高度值代表了第0行到第i行的该位置上连续的1的数量。
* 当我们将每一行转为直方图数组height的时候，就可以单独求出这一行的最大矩形的面积，和题目四的一样。
* 我们从第0行开始，直到数组的最后一行，求每一行的直方图数组中的最大矩形的面积，累计出来的最大值，就是题目要求的最大矩形的面积。
* <br>
* 压缩数组的求法：
* 1、第0行的压缩数组和原数组第0行是一样的
* 2、从第1行开始，如果记当前行为i，原数组为arr，当前压缩位置为j，则压缩数组height[j]位置的值如下：
* 2.1、如果arr[i][j] == 0,则压缩数组当前位置的值为0，即height[j] = 0
* 2.2、如果arr[i][j] == 1,则压缩数组当前位置的值为当前的值加一，即height[j] = height[j] + 1
* 通过压缩数组的求法，可以直观的看出压缩数组每个位置的值代表了前面连续的1的个数。
*/
public static int maximalRectangle(char[][] map) {
if (map == null || map.length == 0 || map[0].length == 0) {
return 0;
}
int maxArea = 0;
// 压缩数组
int[] height = new int[map[0].length];
// 因为java中数组默认为0，所以可以将压缩数组的第0行和其他行一样的方式求解
for (int i = 0; i < map.length; i++) {
// 先填充压缩数组
for (int j = 0; j < map[0].length; j++) {
height[j] = map[i][j] == '0' ? 0 : height[j] + 1;
}
// 求出每个压缩数组的最大矩形面积
maxArea = Math.max(maxRecFromBottom(height), maxArea);
}
return maxArea;
}
/**
* 利用单调栈的方法，求出每个压缩数组height的最大矩形面积
* 这里我们直接用数组单调栈的写法，提升效率
*/
public static int maxRecFromBottom(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int maxArea = 0;
int stackIndex = -1;
int[] stack = new int[height.length];
for (int i = 0; i < height.length; i++) {
// 结算比当前值大的位置
while (stackIndex > -1 && height[stack[stackIndex]] >= height[i]) {
int j = stack[stackIndex--];
int k = stackIndex == -1 ? -1 : stack[stackIndex];
int curArea = (i - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
// 入栈当前位置
stack[++stackIndex] = i;
}
// 结算剩余位置
while (stackIndex > -1) {
int j = stack[stackIndex--];
int k = stackIndex == -1 ? -1 : stack[stackIndex];
int curArea = (height.length - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
}
2.6、题目六：统计全为1的子矩形数量
- 题目六：统计全为1的子矩形数量
- 给定一个二维数组matrix，其中的值不是0就是1，
- 返回全部由1组成的子矩形的数量
- 测试链接：https://leetcode.cn/problems/count-submatrices-with-all-ones
2.6.1 压缩数组+单调栈的解法
- 压缩数组+单调栈的方法
- 思路：
- 本题和题目五都是一个二维数组，但是题目五求的是值为1的最大矩形的面积，这里求的是值为1的子矩阵的数量。
- 本题和题目五都是一个二维数组，但是题目五求的是值为1的最大矩形的面积，这里求的是值为1的子矩阵的数量。
- 子矩阵数量的求法：
- 首先我们要明白，如果一个数组长为n，高为h，其内部都是1，那么这个数组有多少个子矩阵数组呢？
- 如果高h为1，则矩阵的个数是依靠下边来组合的，即成了一维数组的子数组个数，公式为：n*(n+1)/2
- 如果高超过1呢？因为矩阵必须是从一个点到另一个点，中间的面积都要包括，所以高的维度不存在排列组合的问题。
- 所以高为h的矩阵个数就是一维的子数组个数乘以高h，公式为：n*(n+1)/2 * h
- 想明白了全1矩阵的子矩阵的算法，接下来我们可以把二维数组进来分成多个包含1的全1矩阵，然后用公式求解就可以求出个数了。
- 全1矩阵的计算问题：
- 我们根据题目五的思路，先将二维矩阵转成一个压缩数组，每一行的压缩数组代表了该行为底的1的直方图。
- 然后我们根据单调栈的方法，对于每一个位置的值，将该位置的值看成是全1矩阵的高，就可以求出高是当前值的全1矩阵的范围了。
- 但是求出了全1的范围，我们还不能直接利用公式算出子矩阵的数量，因为会多算。
- 比如当前值是3，让它出单调栈的值为2，如果我们直接用3为高来计算出子矩阵的个数的话，当到值为2的这个高弹出的时候，
- 我们还会重新计算高为2的数组的个数，因为2比3小，所以高为2的矩阵的边肯定要比高为3的矩阵的边要长，这个时候两个矩阵就会有交集，算出来的个数就会多。
- 那我们应该怎么算呢？
- 其实我们只需要在每次弹出来的时候，只计算两个高的差值所形成的矩阵的个数，这样到高比较小的弹出的时候，会将底下的数组也算了，这样就不会超了。
/**
* 题目六：统计全为1的子矩形数量
* 给定一个二维数组matrix，其中的值不是0就是1，
* 返回全部由1组成的子矩形的数量
* 测试链接：https://leetcode.cn/problems/count-submatrices-with-all-ones
*/
public class Q6_CountSubmatricesWithAllOnes {
/**
* 压缩数组+单调栈的方法
* 思路：
* 本题和题目五都是一个二维数组，但是题目五求的是值为1的最大矩形的面积，这里求的是值为1的子矩阵的数量。
* <br>
* 子矩阵数量的求法：
* 首先我们要明白，如果一个数组长为n，高为h，其内部都是1，那么这个数组有多少个子矩阵数组呢？
* 如果高h为1，则矩阵的个数是依靠下边来组合的，即成了一维数组的子数组个数，公式为：n*(n+1)/2
* 如果高超过1呢？因为矩阵必须是从一个点到另一个点，中间的面积都要包括，所以高的维度不存在排列组合的问题。
* 所以高为h的矩阵个数就是一维的子数组个数乘以高h，公式为：n*(n+1)/2 * h
* 想明白了全1矩阵的子矩阵的算法，接下来我们可以把二维数组进来分成多个包含1的全1矩阵，然后用公式求解就可以求出个数了。
* <br>
* 全1矩阵的计算问题：
* 我们根据题目五的思路，先将二维矩阵转成一个压缩数组，每一行的压缩数组代表了该行为底的1的直方图。
* 然后我们根据单调栈的方法，对于每一个位置的值，将该位置的值看成是全1矩阵的高，就可以求出高是当前值的全1矩阵的范围了。
* 但是求出了全1的范围，我们还不能直接利用公式算出子矩阵的数量，因为会多算。
* 比如当前值是3，让它出单调栈的值为2，如果我们直接用3为高来计算出子矩阵的个数的话，当到值为2的这个高弹出的时候，
* 我们还会重新计算高为2的数组的个数，因为2比3小，所以高为2的矩阵的边肯定要比高为3的矩阵的边要长，这个时候两个矩阵就会有交集，算出来的个数就会多。
* 那我们应该怎么算呢？
* 其实我们只需要在每次弹出来的时候，只计算两个高的差值所形成的矩阵的个数，这样到高比较小的弹出的时候，会将底下的数组也算了，这样就不会超了。
*
*/
public static int numSubmat(int[][] mat) {
if (mat == null || mat.length == 0 || mat[0].length == 0) {
return 0;
}
int nums = 0;
// 压缩数组
int[] height = new int[mat[0].length];
// 填充每一行的压缩数组，然后求出举证数量，累加起来就是最终的结果
for (int i = 0; i < mat.length; i++) {
// 填充压缩数组
for (int j = 0; j < mat[0].length; j++) {
height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;
}
// 计算当前行的子矩阵数量
nums += countSubmatrices(height);
}
return nums;
}
/**
* 利用单调栈算出当前压缩数组的子矩阵个数
*/
public static int countSubmatrices(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int nums = 0;
// 数组单调栈
int si = -1;
int[] stack = new int[height.length];
for (int i = 0; i < height.length; i++) {
while (si > -1 && height[stack[si]] >= height[i]) {
// 此时弹出的栈顶元素就是当前的高度
int cur = stack[si--];
// 左侧的边界
int left = si == -1 ? -1 : stack[si];
// 底边的范围,i为右侧边界，left为左侧边界，n为底边的长度
int n = i - left - 1;
// 求出当前的下边界，将下边界的算法留到后面算，防止算重，下边界就是当前的i和left边界的较大值
int down = Math.max(left == -1 ? 0 : height[left], height[i]);
// 计算出当前的数量,用位移代替除法，比较高效
nums += (height[cur] - down) * (n * (n + 1) >> 1);
}
stack[++si] = i;
}
// 清算栈中剩余的元素
while (si > -1) {
int cur = stack[si--];
int left = si == -1 ? -1 : stack[si];
int n = height.length - left - 1;
int down = left == -1 ? 0 : height[left];
nums += (height[cur] - down) * (n * (n + 1) >> 1);
}
return nums;
}
}
2.7、题目七：子数组的最小值之和
- 题目七：子数组的最小值之和
- 给定一个数组arr，返回所有子数组最小值的累加和
- 由于答案可能很大，因此返回答案模10^9 + 7
- 测试链接：https://leetcode.cn/problems/sum-of-subarray-minimums/
2.7.1 暴力方法
- 暴力解法：
- 找出所有的子数组，然后遍历出最小值，累加起来。
- 提交时名称改为：sumSubarrayMins ，会超时
- 找出所有的子数组，然后遍历出最小值，累加起来。
/**
* 暴力解法：
* 找出所有的子数组，然后遍历出最小值，累加起来。
* <br>
* 提交时名称改为：sumSubarrayMins ，会超时
*/
public static int sumSubarrayMins1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
long ans = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
int min = arr[i];
for (int k = i + 1; k <= j; k++) {
min = Math.min(min, arr[k]);
}
ans += min;
}
}
return (int) (ans % 1000000007);
}
2.7.2 没用单调栈的最优解思路
- 没用单调栈的最优解思路：
- 本题求解的是所有子数组的最小值的累加和，我们首先要求的就是最小值，然后就是子数组的边界，最后要根据这个条件求出子数组的数量。最后累加起来。
- 如果我们假定arr[i]为最小值，我们可以求出左右两边的边界，但如何求出其数量呢？
- 比如一个数组[4,10,8,9,6,7,12,5]
- 下标为------0 1 2 3 4 5 6 7
- 假设我们目前假定的是4位置的6为最小值，那么左右边界就是0和7，因为假定的是以4位置的6为最小值，所以子数组必须包含这个位置。
- 所以对于位置1、2、3、4这三个位置，各有包含位置4、5、6这几种组合，合计是3*3 =9 种情况
- 对于位置4开始的，有4、5、6这三种，合计是3种情况，总共加起来就是9+3=12种情况。即(4-0)*(7-4)=12
- 所以我们推广一下，对于某个位置i的两个边界，其数量为(i-left)*(right-i)
- 上面的示例是没有重复值的情况，如果加上重复值，我们只需要将重复值包含到左边界或者右边界即可，不能同时包含在左右边界，因为会重复计算。
- 这也就是意味着，不能一次性求出某个位置的左右边界，因为有一侧要包含重复值，我们要单独求出左边界或者右边界。形成两个数组，进行两次求解。
- 本示例中都是将重复值包含在左边界。
- 在分别计算左右边界的时候，我们可以直接求解，也可以使用单调栈求解。
- 本方法我们先演示直接求解的情况，直接求解就比较简单，到了某个位置，直接往需要的方向走找到合适的值就行。
- 提交时名称改为：sumSubarrayMins
/**
* 没用单调栈的最优解思路：
* 本题求解的是所有子数组的最小值的累加和，我们首先要求的就是最小值，然后就是子数组的边界，最后要根据这个条件求出子数组的数量。最后累加起来。
* 如果我们假定arr[i]为最小值，我们可以求出左右两边的边界，但如何求出其数量呢？
* 比如一个数组[4,10,8,9,6,7,12,5]
* 下标为------0 1 2 3 4 5 6 7
* 假设我们目前假定的是4位置的6为最小值，那么左右边界就是0和7，因为假定的是以4位置的6为最小值，所以子数组必须包含这个位置。
* 所以对于位置1、2、3、4这三个位置，各有包含位置4、5、6这几种组合，合计是3*3 =9 种情况
* 对于位置4开始的，有4、5、6这三种，合计是3种情况，总共加起来就是9+3=12种情况。即(4-0)*(7-4)=12
* 所以我们推广一下，对于某个位置i的两个边界，其数量为(i-left)*(right-i)
* 上面的示例是没有重复值的情况，如果加上重复值，我们只需要将重复值包含到左边界或者右边界即可，不能同时包含在左右边界，因为会重复计算。
* 这也就是意味着，不能一次性求出某个位置的左右边界，因为有一侧要包含重复值，我们要单独求出左边界或者右边界。形成两个数组，进行两次求解。
* 本示例中都是将重复值包含在左边界。
* 在分别计算左右边界的时候，我们可以直接求解，也可以使用单调栈求解。
* 本方法我们先演示直接求解的情况，直接求解就比较简单，到了某个位置，直接往需要的方向走找到合适的值就行。
* <br>
* 提交时名称改为：sumSubarrayMins
*/
public static int sumSubarrayMins2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
// left[i] = x : arr[i]左边，离arr[i]最近，<=arr[i]，位置在x
int[] left = leftNearLessEqual2(arr);
// right[i] = y : arr[i]右边，离arr[i]最近，< arr[i],的数，位置在y
int[] right = rightNearLess2(arr);
long ans = 0;
// 按照公式计算结果
for (int i = 0; i < arr.length; i++) {
int start = i - left[i];
int end = right[i] - i;
ans += (long) start * end * arr[i];
}
return (int) (ans % 1000000007);
}
/**
* 直接求解左边界(包含)：
* 从左遍历数组，对于每个位置i，我们从i-1开始往左遍历，找到第一个小于等于arr[i]的位置，就是左边界。
* 如果遍历到了数组的最左边，还没有找到，那么左边界就是-1。
*/
private static int[] leftNearLessEqual2(int[] arr) {
int[] left = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
int ans = -1;
for (int j = i - 1; j >= 0; j--) {
if (arr[j] <= arr[i]) {
ans = j;
break;
}
}
left[i] = ans;
}
return left;
}
/**
* 直接求解右边界(不包含)：
* 从右遍历数组，对于每个位置i，我们从i+1开始往右遍历，找到第一个小于arr[i]的位置，就是右边界。
* 如果遍历到了数组的最右边，还没有找到，那么右边界就是数组的长度。
*/
public static int[] rightNearLess2(int[] arr) {
int N = arr.length;
int[] right = new int[N];
for (int i = 0; i < N; i++) {
int ans = N;
for (int j = i + 1; j < N; j++) {
if (arr[i] > arr[j]) {
ans = j;
break;
}
}
right[i] = ans;
}
return right;
}
2.7.3 最优解思路下的单调栈优化
- 最优解思路下的单调栈优化：
- 思路：
- 基于上面的解法，在求左右边界的时候，我们用单调栈的方法来求解。
- 提交时名称改为：sumSubarrayMins
- 基于上面的解法，在求左右边界的时候，我们用单调栈的方法来求解。
/**
* 最优解思路下的单调栈优化：
* 思路：
* 基于上面的解法，在求左右边界的时候，我们用单调栈的方法来求解。
* <br>
* 提交时名称改为：sumSubarrayMins
*/
public static int sumSubarrayMins3(int[] arr) {
int[] stack = new int[arr.length];
int[] left = nearLessEqualLeft3(arr, stack);
int[] right = nearLessRight3(arr, stack);
long ans = 0;
for (int i = 0; i < arr.length; i++) {
long start = i - left[i];
long end = right[i] - i;
ans += start * end * (long) arr[i];
}
return (int) (ans % 1000000007);
}
/**
* 单调栈求解左边界(包含)：
* 因为要包含左边界，所以我们直接从右往左遍历数组，求解左边界。
*/
public static int[] nearLessEqualLeft3(int[] arr, int[] stack) {
int N = arr.length;
int[] left = new int[N];
int size = 0;
for (int i = N - 1; i >= 0; i--) {
while (size != 0 && arr[stack[size - 1]] >= arr[i]) {
left[stack[--size]] = i;
}
stack[size++] = i;
}
while (size != 0) {
left[stack[--size]] = -1;
}
return left;
}
/**
* 单调栈求解右边界(不包含)：
*/
public static int[] nearLessRight3(int[] arr, int[] stack) {
int N = arr.length;
int[] right = new int[N];
int size = 0;
for (int i = 0; i < N; i++) {
while (size != 0 && arr[stack[size - 1]] > arr[i]) {
right[stack[--size]] = i;
}
stack[size++] = i;
}
while (size != 0) {
right[stack[--size]] = N;
}
return right;
}
整体代码和测试：
/**
* 题目七：子数组的最小值之和
* 给定一个数组arr，返回所有子数组最小值的累加和
* 由于答案可能很大，因此返回答案模10^9 + 7
* 测试链接：https://leetcode.cn/problems/sum-of-subarray-minimums/
*/
public class Q7_SumOfSubarrayMinimums {
/**
* 暴力解法：
* 找出所有的子数组，然后遍历出最小值，累加起来。
* <br>
* 提交时名称改为：sumSubarrayMins ，会超时
*/
public static int sumSubarrayMins1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
long ans = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
int min = arr[i];
for (int k = i + 1; k <= j; k++) {
min = Math.min(min, arr[k]);
}
ans += min;
}
}
return (int) (ans % 1000000007);
}
/**
* 没用单调栈的最优解思路：
* 本题求解的是所有子数组的最小值的累加和，我们首先要求的就是最小值，然后就是子数组的边界，最后要根据这个条件求出子数组的数量。最后累加起来。
* 如果我们假定arr[i]为最小值，我们可以求出左右两边的边界，但如何求出其数量呢？
* 比如一个数组[4,10,8,9,6,7,12,5]
* 下标为------0 1 2 3 4 5 6 7
* 假设我们目前假定的是4位置的6为最小值，那么左右边界就是0和7，因为假定的是以4位置的6为最小值，所以子数组必须包含这个位置。
* 所以对于位置1、2、3、4这三个位置，各有包含位置4、5、6这几种组合，合计是3*3 =9 种情况
* 对于位置4开始的，有4、5、6这三种，合计是3种情况，总共加起来就是9+3=12种情况。即(4-0)*(7-4)=12
* 所以我们推广一下，对于某个位置i的两个边界，其数量为(i-left)*(right-i)
* 上面的示例是没有重复值的情况，如果加上重复值，我们只需要将重复值包含到左边界或者右边界即可，不能同时包含在左右边界，因为会重复计算。
* 这也就是意味着，不能一次性求出某个位置的左右边界，因为有一侧要包含重复值，我们要单独求出左边界或者右边界。形成两个数组，进行两次求解。
* 本示例中都是将重复值包含在左边界。
* 在分别计算左右边界的时候，我们可以直接求解，也可以使用单调栈求解。
* 本方法我们先演示直接求解的情况，直接求解就比较简单，到了某个位置，直接往需要的方向走找到合适的值就行。
* <br>
* 提交时名称改为：sumSubarrayMins
*/
public static int sumSubarrayMins2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
// left[i] = x : arr[i]左边，离arr[i]最近，<=arr[i]，位置在x
int[] left = leftNearLessEqual2(arr);
// right[i] = y : arr[i]右边，离arr[i]最近，< arr[i],的数，位置在y
int[] right = rightNearLess2(arr);
long ans = 0;
// 按照公式计算结果
for (int i = 0; i < arr.length; i++) {
int start = i - left[i];
int end = right[i] - i;
ans += (long) start * end * arr[i];
}
return (int) (ans % 1000000007);
}
/**
* 直接求解左边界(包含)：
* 从左遍历数组，对于每个位置i，我们从i-1开始往左遍历，找到第一个小于等于arr[i]的位置，就是左边界。
* 如果遍历到了数组的最左边，还没有找到，那么左边界就是-1。
*/
private static int[] leftNearLessEqual2(int[] arr) {
int[] left = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
int ans = -1;
for (int j = i - 1; j >= 0; j--) {
if (arr[j] <= arr[i]) {
ans = j;
break;
}
}
left[i] = ans;
}
return left;
}
/**
* 直接求解右边界(不包含)：
* 从右遍历数组，对于每个位置i，我们从i+1开始往右遍历，找到第一个小于arr[i]的位置，就是右边界。
* 如果遍历到了数组的最右边，还没有找到，那么右边界就是数组的长度。
*/
public static int[] rightNearLess2(int[] arr) {
int N = arr.length;
int[] right = new int[N];
for (int i = 0; i < N; i++) {
int ans = N;
for (int j = i + 1; j < N; j++) {
if (arr[i] > arr[j]) {
ans = j;
break;
}
}
right[i] = ans;
}
return right;
}
/**
* 最优解思路下的单调栈优化：
* 思路：
* 基于上面的解法，在求左右边界的时候，我们用单调栈的方法来求解。
* <br>
* 提交时名称改为：sumSubarrayMins
*/
public static int sumSubarrayMins3(int[] arr) {
int[] stack = new int[arr.length];
int[] left = nearLessEqualLeft3(arr, stack);
int[] right = nearLessRight3(arr, stack);
long ans = 0;
for (int i = 0; i < arr.length; i++) {
long start = i - left[i];
long end = right[i] - i;
ans += start * end * (long) arr[i];
}
return (int) (ans % 1000000007);
}
/**
* 单调栈求解左边界(包含)：
* 因为要包含左边界，所以我们直接从右往左遍历数组，求解左边界。
*/
public static int[] nearLessEqualLeft3(int[] arr, int[] stack) {
int N = arr.length;
int[] left = new int[N];
int size = 0;
for (int i = N - 1; i >= 0; i--) {
while (size != 0 && arr[stack[size - 1]] >= arr[i]) {
left[stack[--size]] = i;
}
stack[size++] = i;
}
while (size != 0) {
left[stack[--size]] = -1;
}
return left;
}
/**
* 单调栈求解右边界(不包含)：
*/
public static int[] nearLessRight3(int[] arr, int[] stack) {
int N = arr.length;
int[] right = new int[N];
int size = 0;
for (int i = 0; i < N; i++) {
while (size != 0 && arr[stack[size - 1]] > arr[i]) {
right[stack[--size]] = i;
}
stack[size++] = i;
}
while (size != 0) {
right[stack[--size]] = N;
}
return right;
}
public static void main(String[] args) {
int maxLen = 100;
int maxValue = 50;
int testTime = 100000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int len = (int) (Math.random() * maxLen);
int[] arr = randomArray(len, maxValue);
int ans1 = sumSubarrayMins1(arr);
int ans2 = sumSubarrayMins2(arr);
int ans3 = sumSubarrayMins3(arr);
if (ans1 != ans2 || ans1 != ans3) {
System.out.println("出错了！");
printArray(arr);
System.out.printf("ans1: %d, ans2: %d, ans3: %d\n", ans1, ans2, ans3);
break;
}
}
System.out.println("测试结束");
}
public static int[] randomArray(int len, int maxValue) {
int[] ans = new int[len];
for (int i = 0; i < len; i++) {
ans[i] = (int) (Math.random() * maxValue) + 1;
}
return ans;
}
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
后记
个人学习总结笔记，不能保证非常详细，轻喷
更多推荐
11
0- 0
已为社区贡献3条内容
所有评论(0)