[数据结构与算法]csp题集《最大的矩形》-Java

?

思路：贪心算法

遍历数组记录，只记录每次最大面积值。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int maxS = 0;
        for (int i = 0; i < n; i++) {
            int s = 0;
            //  矩形的底
            int l = 1;
            int h = nums[i];
            for (int j = i; j < n; j++) {
                //  选取最矮的高
                h = Math.min(h, nums[j]);
                //  贪心
                s = Math.max(s, l * h);
                l++;
                //
                if (s >= maxS) maxS = s;
            }
        }
        System.out.println(maxS);
    }
}

?