陣列墻 最詳細的解題報告

題目

隨機給定一個整型陣列，每個陣列中的數字代表陣列所在位置墻的高度，問這個陣列所能拼湊的最大矩形墻的面積為多少，

示例

• 輸入：{2, 1, 6, 5, 4, 7, 2}
• 輸出：16

提示

陣列{2, 1, 6, 5, 4, 7, 2}可以描述為：

其中，

• 第一行的數字表示陣列中對應的值
• 每一列中\(\color{#000000}{*}\)的個數加上\(\color{#FF3030}{*}\)的個數之和等于第一行中陣列的值
• \(\color{#FF3030}{*}\)表示最大的矩形墻面積

解題思路

1. 將原陣列array復制一份到陣列copy
2. 新建一個陣列area用來存盤包含當前列的最大面積，初始值為0
3. 將陣列copy按0元素切割成多個子陣列用Coordinate物件來表示，其中Coordinate.startIndex表示子陣列的起始下標，Coordinate.endIndex表示子陣列的結束下標（但不包含），Coordinate.minValue表示子陣列的最小值
4. 將陣列copy[i]中的值減去Coordinate.minValue，其中Coordinate.startIndex <= i < Coordinate.endIndex，根據陣列area的值area[i] = Math.max(area[i], (array[i] - copy[i]) * (Coordinate.endIndex - Coordinate.startIndex))
5. 重復3)和4)遍歷所有的Coordinate物件，直到按0元素切割不能獲得有效Coordinate

具體演算法（Java版）

public class FindMaxRectangle {

    public static void main(String[] args) {
        // 隨機生成陣列
        int[] array = generateArray(20);
        // 將陣列列印出來
        System.out.println("當前陣列：" + arrayToString(array));
        // 列印陣列墻
        printArray(array);
        // 輸出最大矩形墻的面積
        System.out.println("陣列最大矩形墻的面積為：" + findMax(array));
    }

    /**
     * 查找最大矩形墻的面積
     */
    private static int findMax(int[] array) {
        int[] copy = new int[array.length]; // 記錄運行時陣列中的值
        int[] area = new int[array.length]; // 記錄最大矩形墻的面積
        Queue<List<Coordinate>> queue = new LinkedList<>();
        for (int i = 0; i < array.length; i++) {
            copy[i] = array[i];
            area[i] = 0;
        }
        queue.offer(divideArray(copy));
        while (!queue.isEmpty()) {
            List<Coordinate> coordinates = queue.poll();
            // 沒有任何有效的子陣列
            if (coordinates.size() == 0)
                break;
            for (Coordinate coordinate : coordinates) {
                for (int i = coordinate.getStartIndex(); i < coordinate.getEndIndex(); i++) {
                    if (copy[i] > 0) {
                        // 減去最小值minValue
                        copy[i] -= coordinate.getMinValue();
                    }
                    // 計算子陣列對應的最大矩陣墻面積
                    int value = https://www.cnblogs.com/pinxiong/p/(array[i] - copy[i]) *
                            (coordinate.getEndIndex() - coordinate.getStartIndex());
                    // 更新最大矩陣墻的面積
                    area[i] = Math.max(value, area[i]);
                }
            }
            queue.offer(divideArray(copy));
        }
        // 查找最大的矩陣墻的面積
        int maxArea = 0;
        for (int i = 0; i < area.length; i++) {
            if (maxArea < area[i]) {
                maxArea = area[i];
            }
        }
        return maxArea;
    }

    /**
     * 將陣列按照0元素切分成多個子陣列，子陣列用Coordinate物件來記錄
     */
    private static List divideArray(int[] array) {
        List coordinates = new ArrayList<>();
        int startIndex = -1, endIndex = -1, minValue = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            if (array[i] != 0) {
                if (startIndex == -1) {
                    startIndex = i;
                }
                if (array[i] < minValue) {
                    minValue = array[i];
                }
            } else {
                if (startIndex != -1) {
                    endIndex = i;
                    coordinates.add(new Coordinate(startIndex, endIndex, minValue));
                    startIndex = -1;
                    minValue = Integer.MAX_VALUE;
                }
            }
        }
        if (startIndex != -1) {
            coordinates.add(new Coordinate(startIndex, array.length, minValue));
        }
        return coordinates;
    }

    /**
     * 隨機生成指定長度的陣列
     */
    private static int[] generateArray(int length) {
        int[] array = new int[length];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            int value = random.nextInt(10);
            if (value < 0) {
                value = 0;
            }
            array[i] = value;
        }
        return array;
    }

    /**
     * 列印成陣列墻
     */
    private static void printArray(int[] array) {
        int max = 0;
        for (int i = 0; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        for (int i = max; i > 0; i--) {
            for (int j = 0; j < array.length; j++) {
                if (array[j] >= i) {
                    System.out.print("* ");
                } else {
                    System.out.print("  ");
                }
            }
            System.out.println();
        }
    }

    /**
     * 將陣列轉換成字串
     */
    private static String arrayToString(int[] array) {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < array.length; i++) {
            stringBuilder.append(array[i]);
            if (i != array.length - 1) {
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    /**
     * 用來記錄子陣列資訊
     */
    static class Coordinate {
        /**
         * @param startIndex 陣列的起始下標
         * @param endIndex 陣列的結束下標（不包含）
         * @param minValue 陣列中的最小值
         */
        public Coordinate(int startIndex, int endIndex, int minValue) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
            this.minValue = minValue;
        }

        private int startIndex; // 陣列的起始下標
        private int endIndex; // 陣列的結束下標（不包含）
        private int minValue; // 陣列中的最小值

        public int getStartIndex() {
            return startIndex;
        }

        public int getEndIndex() {
            return endIndex;
        }

        public int getMinValue() {
            return minValue;
        }
    }
}

輸出結果

如果大家有什么更好的方法或者發現代碼中存在bug希望可以一起交流討論！

標籤：其他

上一篇：CF 1362C Johnny and Another Rating Drop

下一篇：UVa140(帶寬)