牛客2024 【牛客&赛文X】春招冲刺 ONT84 子数组的最小值之和【中等 单调栈 Java、Go、PHP】
题目
题目链接：
https://www.nowcoder.com/practice/a7401d0dd4ec4071a31fd434e150bcc2
思路
单调栈解决的问题
单调栈解决的问题是在一个数组中想知道所有数中，
左边离他近的比他大的和右边离他近的比他大的数
思考的问题：如果知道所有数上得到上述要求，
同时复杂度满足O(N)。
单调栈结构：单调栈内，从栈底到栈顶满足从大到小。
例如：5（0）4（1）3（2）6（3）后面括号代表所属位置
原文链接：https://blog.csdn.net/qq_35065720/article/details/104211981
参考答案Java
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int sumSubarr (ArrayList<Integer> ll) {
int[] nums = new int[ll.size()];
for (int i=0;i<ll.size();i++){
nums[i] = ll.get(i);
}
//力扣同一道题：
//https://leetcode.cn/problems/sum-of-subarray-minimums/description/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
//单调栈
int[] left = left(nums);
int[] right = right(nums);
long max = 0;
for (int i = 0; i <nums.length ; i++) {
//max +=nums[i]*(right[i]-left[i]+1);
// max +=nums[i]*(right[i]-left[i]+1);
int start = i-left[i];
int end = right[i]-i;
max+= start*end*(long)nums[i];
max%=1000000007;
}
return (int) max;
}
public int[] left(int[] arr){//往左扩
int n= arr.length;
int[] ans = new int[n];
Stack<Integer> stk = new Stack<>();
for (int i = n-1; i >=0 ; i--) {
while (!stk.isEmpty() && arr[stk.peek()] >= arr[i]){
ans[stk.pop()] = i;
}
stk.add(i);
}
while (!stk.isEmpty()){
ans[stk.pop()] = -1;
}
return ans;
}
public int[] right(int[] arr){ //往右扩
int n = arr.length;
int[] ans = new int[n];
Stack<Integer> stk = new Stack<>();
for (int i = 0; i <n ; i++) {
while (!stk.isEmpty() && arr[stk.peek()] > arr[i]){
ans[stk.pop()] = i;
}
stk.add(i);
}
while (!stk.isEmpty()){
ans[stk.pop()] = n;
}
return ans;
}
}
参考答案Go
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
func sumSubarr( nums []int ) int {
//单调栈
n := len(nums)
left := left(nums)
right := right(nums)
ans := 0
for i := 0; i < n; i++ {
start := i - left[i]
end := right[i] - i
ans += start * end * nums[i]
ans %= 1000000007
}
return ans
}
func left(arr []int) []int { //往左扩
n := len(arr)
ans := make([]int, n)
stk := []int{}
for i := n - 1; i >= 0; i-- {
for len(stk) > 0 && arr[stk[len(stk)-1]] >= arr[i] {
ans[stk[len(stk)-1]] = i
stk = stk[:len(stk)-1]
}
stk = append(stk, i)
}
for len(stk) != 0 {
ans[stk[len(stk)-1]] = -1
stk = stk[:len(stk)-1]
}
return ans
}
func right(arr []int) []int { //往右扩
n := len(arr)
ans := make([]int, n)
stk := []int{}
for i := 0; i < n; i++ {
for len(stk) != 0 && arr[stk[len(stk)-1]] > arr[i] {
ans[stk[len(stk)-1]] = i
stk = stk[:len(stk)-1]
}
stk = append(stk, i)
}
for len(stk) != 0 {
ans[stk[len(stk)-1]] = n
stk = stk[:len(stk)-1]
}
return ans
}
参考答案PHP
<?php
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
function sumSubarr( $nums )
{
//单调栈
$n = count($nums);
$left = left($nums);
$right = right($nums);
$ans = 0;
for($i=0;$i<$n;$i++){
$start = $i-$left[$i];
$end = $right[$i]-$i;
$ans += $start*$end*$nums[$i];
$ans %=1000000007;
}
return $ans;
}
function left($arr){
$n = count($arr);
$ans = [];
$s =[];
for($i=$n-1;$i>=0;$i--){
while ( count($s)!=0 && $arr[$s[count($s)-1]] >= $arr[$i]){
$ans[array_pop($s)] = $i;
}
array_push($s,$i);
}
while ( count($s)!=0){
$ans[array_pop($s)] = -1;
}
return $ans;
}
function right($arr){
$n = count($arr);
$ans = [];
$s =[];
for($i=0;$i<$n;$i++){
while ( count($s)!=0 && $arr[$s[ count($s)-1]] > $arr[$i]){
$ans[array_pop($s)] = $i;
}
array_push($s,$i);
}
while ( count($s)!=0){
$ans[array_pop($s)] = $n;
}
return $ans;
}
原文地址：https://blog.csdn.net/weixin_37991016/article/details/137838128
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！