岛

题目

链接：2014. 岛 - AcWing题库

每当下雨时，农夫约翰的田地总是被洪水淹没。

由于田地不是完全水平的，所以一些地方充满水后，留下了许多被水隔开的“岛”。

约翰的田地被描述为由 N 个连续高度值 H1,…,HN 指定的一维场景。

假设该场景被无限高的围墙包围着，请考虑暴雨期间发生的情况：

最低处首先被水覆盖，形成一些不连贯的岛，随着水位的不断上升，这些岛最终都会被覆盖。

一旦水位等于一块田地的高度，那块田地就被认为位于水下。

上图显示了一个示例：在左图中，我们只加入了刚好超过 1 单位的水，此时剩下 4 个岛（最大岛屿剩余数量），而在右图中，我们共加入了 7 单位的水，此时仅剩下 22个岛。

请计算，暴风雨期间我们能在某个时间点看到的最大岛屿数量。

水会一直上升到所有田地都在水下。

代码

import java.util.*;
class node implements Comparable<node>{
    int h, poit;
    public node(int h, int poit)
    {
        this.h = h;
        this.poit = poit;
    }
    @Override
    public int compareTo(node o) {
        return h - o.h;
    }
}
public class Main {
    static int n = 0;
    static int[] a = new int[100010];
    static node[] v = new node[100100];
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        int nn, cnt = 0;
        nn = inScanner.nextInt();
        for(int i = 1; i <= nn; i ++)
        {
            int b;
            b = inScanner.nextInt();
            if(b != a[n])
            {
                a[++ n] = b;
                v[cnt ++] = new node(a[n], n);
            }
        }
        a[n + 1] = 0;
        inScanner.close();
        Arrays.sort(v, 0, cnt);;
        int res = 1, ans = 0;
        v[cnt] = new node(0, 0);
        for(int i = 0; i < cnt; i ++)
        {
            int j = v[i].poit;
            if(a[j - 1] > a[j] && a[j] < a[j + 1])
                res ++;
            else if(a[j - 1] < a[j] && a[j] > a[j + 1])
                res --;
            if(v[i].h != v[i + 1].h)
                ans = Math.max(ans, res);
        }
        System.out.println(ans);
    }
}
/*
8
3
5
2
3
1
4
2
3
*/