牛客2024【牛客&赛文X】春招冲刺ONT61 每日温度【hard 单调栈 Java、Go、PHP】

题目

题目链接：
https://www.nowcoder.com/practice/1f54e163e6944cc7b8759cc09e9c78d8

思路

单调栈最直接的应用就是获取数组中每个位置i,i的左边第一个比i大或者小的位置/数
以及,i的右边第一个比i大或者小的位置/数

  不懂的同学看这里https://blog.csdn.net/Borslav/article/details/125469491

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 每日温度
     * @param dailyTemperatures int整型一维数组
     * @return int整型一维数组
     */
    public int[] temperatures (int[] dailyTemperatures) {
        //单调栈，递减栈
        // 也就是先求每个元素i左边，右边离他最近的第一个大于i的数,没有大于i的用-1表示

        int n = dailyTemperatures.length;
        int[][] bigarr = new int[n][2];
        //单调递减栈
        Stack<List<Integer>> stack = new Stack<>();
        for (int i = 0; i < n ; i++) {
            while (!stack.isEmpty() &&
                    dailyTemperatures[stack.peek().get(0)] < dailyTemperatures[i]) {
                List<Integer> pops = stack.pop();
                int leftBigger = stack.isEmpty() ? -1 : stack.peek().get(
                                     stack.peek().size() - 1);
                for (Integer pop : pops) {
                    bigarr[pop][0] = leftBigger; //pop左边边第一个比pop大的位置
                    bigarr[pop][1] = i; //pop右边第一个比pop大的位置
                }
            }

            if (!stack.isEmpty() &&
                    dailyTemperatures[stack.peek().get(0)] == dailyTemperatures[i]) {
                stack.peek().add(i);
            } else {
                List<Integer> ll = new ArrayList<>();
                ll.add(i);
                stack.push(ll);
            }
        }

        while (!stack.isEmpty()) {
            List<Integer> pops = stack.pop();
            int leftBigger = stack.isEmpty() ? -1 : stack.peek().get(
                                 stack.peek().size() - 1);
            for (Integer pop : pops) {
                bigarr[pop][0] = leftBigger;
                bigarr[pop][1] = -1;
            }
        }

        //前面的代码是通用的单调栈的模板，
        // 答案中我们只需要用到bigarr中每个元素的1下标，即右边第一个比自己大的位置

        int[] ans = new int[n];
        for (int i = 0; i < n ; i++) {
            if (bigarr[i][1] == -1) {
                ans[i] = 0;
            } else {
                ans[i] = bigarr[i][1] - i;
            }
        }

        return ans;
    }
}

参考答案Go

package main



/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 每日温度
 * @param dailyTemperatures int整型一维数组
 * @return int整型一维数组
 */
func temperatures(dailyTemperatures []int) []int {
//单调栈，递减栈
// 也就是先求每个元素i左边，右边离他最近的第一个大于i的数,没有大于i的用-1表示
n := len(dailyTemperatures)
bigarr := make([][]int, n)
//单调递减栈
stack := [][]int{} //GO中栈用切片表示即可

for i := 0; i < n; i++ {

stlen := len(stack)
for len(stack) > 0 && dailyTemperatures[stack[stlen-1][len(stack[stlen-1])-1]] < dailyTemperatures[i] {
pops := stack[stlen-1]
stack = stack[:stlen-1]

leftbig := 0

if len(stack) == 0 {
leftbig = -1
} else {
stlen = len(stack)
leftbig = stack[stlen-1][len(stack[stlen-1])-1]
}

for _, v := range pops {
bigarr[v] = make([]int, 2)
bigarr[v][0] = leftbig //v左边第一个比v大的位置
bigarr[v][1] = i       //v右边第一个比v大的位置
}
}

stlen = len(stack)
if len(stack) > 0 && dailyTemperatures[stack[stlen-1][len(stack[stlen-1])-1]] == dailyTemperatures[i] {
stack[stlen-1] = append(stack[stlen-1], i)
} else {
list := []int{}
list = append(list, i)
stack = append(stack, list)
}
}

for len(stack) > 0 {
stlen := len(stack)
pops := stack[stlen-1]
stack = stack[:stlen-1]

leftbig := 0
if len(stack) == 0 {
leftbig = -1
} else {
stlen = len(stack)
leftbig = stack[stlen-1][len(stack[stlen-1])-1]
}

for _, v := range pops {
bigarr[v] = make([]int, 2)
bigarr[v][0] = leftbig
bigarr[v][1] = -1
}
}
//前面的代码是通用的单调栈的模板，
// 答案中我们只需要用到bigarr中每个元素的1下标，即右边第一个比自己大的位置
ans := make([]int, n)

for i := 0; i < n; i++ {
if bigarr[i][1] == -1 {
ans[i] = 0
} else {
ans[i] = bigarr[i][1] - i
}
}

return ans
}

参考答案PHP

在这里插入代码片

原文地址：https://blog.csdn.net/weixin_37991016/article/details/137658226

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！