Day59(503, 42)-Toy模板网

这篇具有很好参考价值的文章主要介绍了Day59(503, 42)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

503. Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.

Example 1:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1’s next greater number is 2;
The number 2 can’t find next greater number.
The second 1’s next greater number needs to search circularly, which is also 2.

Example 2:

Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]

class Solution {  
    public int[] nextGreaterElements(int[] nums) {  
        if(nums == null || nums.length <= 1) {  
            return new int[]{-1};  
        }  
        int size = nums.length;  
        int[] result = new int[size];  
        Arrays.fill(result,-1);  
        Stack<Integer> st= new Stack<>();  
        for(int i = 0; i < 2*size; i++) {  
            while(!st.empty() && nums[i % size] > nums[st.peek()]) {  
                result[st.peek()] = nums[i % size];  
                st.pop();  
            }  
            st.push(i % size);  
        }  
        return result;  
    }  
}

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Day59(503, 42)

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9文章来源地址https://www.toymoban.com/news/detail-421069.html

class Solution {  
    public int trap(int[] height) {  
        int length = height.length;  
        if (length <= 2) return 0;  
        int[] maxLeft = new int[length];  
        int[] maxRight = new int[length];  
          
        maxLeft[0] = height[0];  
        for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);  
          
        maxRight[length - 1] = height[length - 1];  
        for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);  
          
        int sum = 0;  
        for (int i = 0; i < length; i++) {  
            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];  
            if (count > 0) sum += count;  
        }  
        return sum;  
    }  
}

到了这里，关于Day59(503, 42)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！