Java题解 | #牛舍的占地面积#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param areas int整型一维数组
     * @return int整型
     */
    public int maxArea (int[] areas) {
        // write code here
        int n = areas.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);

        Deque<Integer> mono_stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!mono_stack.isEmpty() && areas[mono_stack.peek()] >= areas[i]) {
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * areas[i]);
        }
        return ans;
    }
}

该代码使用的编程语言是Java。

该题表达的知识点是使用动态规划求解最长上升子序列（Longest Increasing Subsequence）的问题。给定一个整型数组nums，要求计算出最长上升子序列的长度。具体实现如下：

1. 创建一个长度为数组nums长度的一维数组dp，用来保存以每个元素为结尾的最长上升子序列的长度。
2. 初始化dp数组的所有元素为1，表示每个元素本身就可以构成长度为1的上升子序列。
3. 遍历数组nums，对于每个元素：遍历其之前的所有元素，如果发现比当前元素小的元素，则更新以该元素为结尾的最长上升子序列的长度。如果当前元素大于之前元素，并且以之前元素为结尾的最长上升子序列的长度加1大于以当前元素为结尾的最长上升子序列的长度，那么更新dp数组的对应位置。
4. 遍历dp数组，找到其中的最大值，即为最长上升子序列的长度。
5. 返回最长上升子序列的长度作为最终结果。

代码的文字解释如下：

1. 创建一个长度为输入数组nums长度的一维数组dp，并将其所有元素初始化为1。
2. 遍历输入数组nums的每一个元素：内部再次遍历使用一个指针j，从0到当前元素的索引i-1。如果找到一个比当前元素小的数nums[j]，则更新以nums[i]结尾的最长上升子序列的长度dp[i]为dp[j]+1。
3. 遍历完数组后，找到dp数组中的最大值，即为最长上升子序列的长度。
4. 返回最长上升子序列的长度作为最终结果。