byu_rself

LC.P268[丢失的数字] 方法一：哈希表1234567891011class Solution { public int missingNumber(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) set.add(num); int n = nums.length; for (int i = 0; i <= nums.length; ++i) { if (!set.contains(i)) return i; } return n; }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 方法二：排序12345678910class Solution { public int missingNumber(int[] nums) { Arr ...

LC.P85[最大矩形] 方法一：二维转一维+单调栈将矩阵的每一行看作是柱状图。 示例 [[“1”,”0”,”1”,”0”,”0”], 第一层，高度为[“1”,”0”,”1”,”0”,”0”] [“1”,”0”,”1”,”1”,”1”], 第二层，高度为[“2”,”0”,”2”,”1”,”1”] [“1”,”1”,”1”,”1”,”1”], 第三层，高度为[“3”,”1”,”3”,”2”,”2”] [“1”,”0”,”0”,”1”,”0”]] 第四层，高度为[“4”,”0”,”0”,”3”,”0”] 求出每一层的最大面积可用LC.P84[柱状图中最大的矩形]，并取其中的最大值即为答案。 12345678910111213141516171819202122232425262728293031323334353637383940class Solution { public int maximalRectangle(char[][] matrix) { if (matrix.leng ...

LC.P303[区域和检索-数组不可变] 方法一：前缀和12345678910111213141516171819202122class NumArray { int[] sum; public NumArray(int[] nums) { int n = nums.length; sum = new int[n + 1]; for (int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] + nums[i - 1]; } } public int sumRange(int left, int right) { return sum[right + 1] - sum[left]; }}/** * Your NumArray object will be instantiated and called as such: * NumArray ...

LC.P1090[受标签影响的最大值] 方法一：贪心+排序+哈希表123456789101112131415161718192021class Solution { public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) { int n = values.length; int[][] index = new int[n][2]; for (int i = 0; i < n; ++i) { index[i] = new int[]{values[i], labels[i]}; } Arrays.sort(index, (a, b) -> b[0] - a[0]); Map<Integer, Integer> map = new HashMap<>(); ...

LC.P739[每日温度] 方法一：单调栈123456789101112131415class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; Deque<Integer> stack = new ArrayDeque<>(); int[] ans = new int[n]; for (int i = 0; i < n; ++i) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int index = stack.pop(); ans[index] = i - index; } ...

LC.P1080[根到叶路径上的不足节点] 方法一：DFS123456789101112131415161718192021222324252627282930/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public Tree ...

LC.P795[区间子数组个数] 方法一：单调栈123456789101112131415161718192021222324252627282930313233class Solution { public int numSubarrayBoundedMax(int[] nums, int left, int right) { int n = nums.length; int[] l = new int[n], r = new int[n]; Arrays.fill(l, -1); Arrays.fill(r, n); Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { // 求nums[i]的左侧第一个大于该元素的下标l[i] int num = nums[i]; while ...

LC.P2104[子数组范围和] 方法一：暴力123456789101112131415class Solution { public long subArrayRanges(int[] nums) { long ans = 0; int n = nums.length; for (int i = 0; i < n; ++i) { int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; for (int j = i; j < n; ++j) { min = Math.min(min, nums[j]); max = Math.max(max, nums[j]); ans += max - min; } } return ans; ...

LCP.33[蓄水] 方法一：贪心123456789101112131415class Solution { public int storeWater(int[] bucket, int[] vat) { int max = Arrays.stream(vat).max().getAsInt(); if (max == 0) return 0; int n = vat.length, ans = Integer.MAX_VALUE; for (int i = 1; i <= max; ++i) { // 蓄水次数 int j = 0; // 升级次数 for (int k = 0; k < n; ++k) { j += Math.max(0, (vat[k] + i - 1) / i - bucket[k]); } ans = Math.min( ...

LC.P1373[二叉搜索子树的最大键值和] 方法一：DFS123456789101112131415161718192021222324252627282930313233343536373839/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution &# ...