【每日算法Day 97】两侧最近更大数下标的乘积最值

题目描述

输入一个数组，对于数组中的数a[i]，设其左右两侧第一个比其大的数的下标分别为j和k，如果找不到更大的数就为0。对于数组中所有的数，找到j*k的最大值。

示例

输入：[5,4,3,4,5]
输出：5
解释对于数字4来说，左侧第一次出现的最大值下标为1，右侧第一次出现的最大值的下标为5，二者乘积为5。没有更大的下标乘积了。

解题思路

使用单调栈的方法，找到并记录每一个数左右两侧最近的更大值的下标，最后相乘比较最大值就可以了。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] a = new int[n]; 
            for(int i = 0; i < n; i++){
                a[i] = in.nextInt();
            }
            //使用两个数组存储a[i]左侧和右侧首个比他大的值的下标，使用单调栈的方法去寻找
            long[] firstRMaxIndex = new long[n], firstLMaxIndex = new long[n];
            
            Deque<Integer> rStack = new LinkedList<>();
            for(int i = 0; i < n ; i++){
                while(!rStack.isEmpty() && a[rStack.peek()] < a[i]){
                    firstRMaxIndex[rStack.pop()] = i + 1;
                }
                rStack.push(i);
            }
            
            Deque<Integer> lStack = new LinkedList<>();
            for(int i = n - 1; i >= 0; i--){
                while(!lStack.isEmpty() && a[lStack.peek()] < a[i]){
                    firstLMaxIndex[lStack.pop()] = i + 1;
                }
                lStack.push(i);
            }
            
            long max = firstRMaxIndex[0] * firstLMaxIndex[0];
            for(int i = 1; i < n; i++){
                max = Math.max(max, firstRMaxIndex[i] * firstLMaxIndex[i]);
            }
            System.out.println(max);
        }
    }
}