第一题很简单easy跳过
1. 962. Maximum Width Ramp
题意
Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[
i] <= A[j]. The width of such a ramp is j - i.
Find the maximum width of a ramp in A. If one doesn't exist, return 0.
找到一个数组中A[j] > A[i]，且(j - i)最大的值
这题看起来不难，但是O(n^2)超时，需要复杂度更小的，其实有很多解法
思路
- 解法一：用TreeMap，最简单的一种思路
找到比当前数小的第一次出现的数
即如果存在比当前数小的数了，则不要将当前数放进去了；否则将当前数放进去，可以更新最小值
class Solution {
public int maxWidthRamp(int[] A) {
int res = 0;
int n = A.length;
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < n; i++) {
if (map.floorKey(A[i]) == null) {
map.put(A[i], i);
} else {
res = Math.max(res, i - map.get(map.floorKey(A[i])));
}
}
return res;
}
}
- 解法二 ：排序O(nlogn)： 排序index,然后只要维护每个index前面最小的index就行了
public int maxWidthRamp(int[] A) {
int n = A.length;
Integer[] indexes = new Integer[n];
for (int i = 0; i < n; i++) {
indexes[i] = i;
}
Arrays.sort(indexes, (a, b) -> ((Integer) A[a]).compareTo(A[b]));
int res = 0, minIndex = indexes[0];
for (int i = 0; i < n; i++) {
res = Math.max(res, indexes[i] - minIndex);
minIndex = Math.min(minIndex, indexes[i]);
}
return res;
}
- 解法三 ：单调栈 O(n):
找到左边第一个比它小的数
那么用递增栈还是递减栈呢？=>
如果我们从右向左遍历每个数的话，希望找到左起第一个比该数小的数，也就是希望栈顶是第一个比这个数小的数，=>
那么如果我们能保证栈顶右边的数，都比栈顶的数大，就是对于右边的数来说，栈顶的数就是第一个小于它的数了 =>
可以维护一个递减栈
代码：
class Solution {
public int maxWidthRamp(int[] A) {
Stack<Integer> stack = new Stack<>();
int n = A.length;
for (int i = 0; i < n; i++) {
if (stack.isEmpty() || A[stack.peek()] > A[i]) {
stack.push(i);
}
}
int res = 0;
for (int i = n - 1; i > 0; i--) {
while (!stack.isEmpty() && A[i] >= A[stack.peek()]) {
res = Math.max(res, i - stack.pop());
}
}
return res;
}
}
总结：
2. Minimum Area Rectangle II
题意
Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.
点能组成的最小面积的矩形，边不一定要平行
思路
这道题是939. Minimum Area Rectangle 的follow up，939要求矩形两边平行坐标轴，用hash table解的。该题的话，由于边可以不平行坐标轴，构成矩形的条件需要稍作思考。
- 由于涉及到边不会平行坐标轴，则应该考虑对角线来构成矩形
- 初中数学：对角线相等且平分的四边形是矩形 => 可以借助hash table,key存对角线长度和中点构成的字符串，value存对角线的点
- 知道了对角线的坐标点后，我们得到了矩形的两个对角线坐标，然后用勾股定理求出两个矩形邻边，再相乘就行了;
代码：
class Solution {
public double minAreaFreeRect(int[][] points) {
int len = points.length;
double res = Double.MAX_VALUE;
if (len < 4) return 0.0;
Map<String, List<int[]>> map = new HashMap<>();
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
long dis = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) + (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
double cx = (double)(points[j][0] + points[i][0])/2;
double cy = (double)(points[j][1] + points[i][1])/2;
String key = "" + dis + "+" + cx + "+" + cy;
if (map.get(key) == null) map.put(key, new ArrayList<int[]>());
map.get(key).add(new int[]{i,j});
}
}
for (String key : map.keySet()) {
if (map.get(key).size() > 1) {
List<int[]> list = map.get(key);
int lsize= list.size();
for (int i = 0; i < lsize; i++) {
for (int j = i + 1; j < lsize; j++) {
int p1 = list.get(i)[0];
int p2 = list.get(j)[0];
int p3 = list.get(j)[1];
double temp = Math.sqrt((points[p1][0] - points[p2][0]) * (points[p1][0] - points[p2][0]) + (points[p1][1] - points[p2][1]) * (points[p1][1] - points[p2][1]))* Math.sqrt((points[p1][0] - points[p3][0]) * (points[p1][0] - points[p3][0]) + (points[p1][1] - points[p3][1]) * (points[p1][1] - points[p3][1]));
res = Math.min(res, temp);
}
}
}
}
return res == Double.MAX_VALUE ? 0.0 : res;
}
}
总结
...emmm 加油吧，周赛的历练不够哇，以后坚持周周都要做
看到了大佬的博客，每道题都有题解，量的积累到质的飞跃