头条编程

https://www.nowcoder.com/test/8537279/summary

算法1：排序，Java过不了，得C++，MMP

package toutiao1;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[][]a=new int[n][2];
        int maxY=-1, idx=-1;
        for(int i=0;i<n;i++){
            a[i][0]=sc.nextInt();
            a[i][1]=sc.nextInt();
            if(a[i][1]>maxY) {
                maxY=a[i][1];
                idx=i;
            }
        }
        
        Stack<int[]> st = new Stack<int[]>();
        st.push(a[idx]);
        for(int i=0;i<n;i++) {
            if(i==idx) continue;
            while(!st.isEmpty()) {
                int[] t=st.peek();
                if(!(a[i][0]>t[0] && a[i][1]>t[1])) break;
                st.pop();
            }
            st.push(st.isEmpty()?a[idx]:a[i]);
        }
        
        List<int[]>l=new ArrayList<int[]>();
        while(!st.isEmpty()) l.add(st.pop());
        Collections.sort(l, new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        for(int[] t:l)
            System.out.println(t[0]+" "+t[1]);
    }
}

算法2：单调栈

package toutiao2;

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[]a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        
        int[] sum = new int[n];
        sum[0]=a[0];
        for(int i=1;i<n;i++) sum[i]=sum[i-1]+a[i];
        
        int res=-1;
        Stack<Integer>st=new Stack<Integer>();
        for(int i=0;i<n;i++) {
            if(st.isEmpty()) {
                st.push(i);
            } else {
                if(a[i]>=a[st.peek()]) {
                    st.push(i);
                } else {
                    while(!st.isEmpty() && a[i]<a[st.peek()]) {
                        int t = st.pop();
                        if(st.isEmpty()) {
                            res = Math.max(res, a[t]*(sum[i-1]));
                        } else {
                            res = Math.max(res, a[t]*(sum[i-1]-sum[st.peek()]));
                        }
                    }
                    st.push(i);
                }
            }
        }
        
        System.out.println(res);
    }
}

算法3：模拟一遍