力扣热题8-荷兰旗、柱状图最大矩形
按照leetcode刷一遍:leetcode hot
75. 颜色分类(再看看)
荷兰旗问题:
计数排序-两次扫描
class Solution {
public void sortColors(int[] nums) {
int redCount = 0;
int whiteCount = 0;
int blueCount = 0;
int n = nums.length;
for(int i=0;i<n;i++) {
if(nums[i]==0) redCount++;
else if(nums[i]==1) whiteCount++;
else blueCount++;
}
int idx = 0;
for(int i=0;i<redCount;i++) nums[idx++] = 0;
for(int i=0;i<whiteCount;i++) nums[idx++] = 1;
for(int i=0;i<blueCount;i++) nums[idx++] = 2;
}
}
进阶:
你能想出一个仅使用常数空间的一趟扫描算法吗?
双指针
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
if(n<=1) {
return;
}
// [0,p0) 0
// [p0,i) 1
// (p2,n-1) 2
int p0 = 0;
int p2 = n-1;
int i = 0;
while(i<=p2) {
if(nums[i]==0) {
swap(nums,p0,i);
p0++;
i++;
} else if(nums[i]==1) {
i++;
} else {
// nums[i]==2
swap(nums,p2,i);
p2--;
}
System.out.println(Arrays.toString(nums));
}
}
private void swap(int[] nums,int i,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
76. 最小覆盖子串
过了,但是比较丑陋。滑窗思想没错,就这样。
class Solution {
public String minWindow(String s, String t) {
int[] scount = new int[128];
int[] tcount = new int[128];
if(s.length()<t.length()) {
return "";
}
for(int i=0;i<t.length();i++) {
tcount[t.charAt(i)]++;
}
int tCharCount = 0;
for(int i=0;i<128;i++) {
if(tcount[i]!=0) tCharCount++;
}
int readyCharCount = 0;
int finalLeft = -1;
int finalRight = s.length();
int left = 0;
int i=0;
for(i=0;i<s.length();i++) {
int p = (int)s.charAt(i);
scount[p]++;
if(scount[p]==tcount[p]) {
readyCharCount++;
}
if(readyCharCount==tCharCount&&i-left<finalRight-finalLeft) {
finalRight = i;
finalLeft = left;
break;
}
}
if(i==s.length()) return "";
// 方便去除left
scount[s.charAt(i)]--;
for(;i<s.length();i++) {
int p = (int)s.charAt(i);
scount[p]++;
while(left<i) {
int leftc = (int)s.charAt(left);
if(scount[leftc]>tcount[leftc]) {
scount[leftc]--;
left++;
} else {
break;
}
}
//System.out.println(s.substring(left,i+1));
if(i-left<finalRight-finalLeft) {
finalRight = i;
finalLeft = left;
}
}
return finalLeft==-1?"":s.substring(finalLeft,finalRight+1);
}
}
78. 子集
递归
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Deque<Integer> deque = new LinkedList<>();
subsetsHelper(nums,result,deque,0);
return result;
}
private void subsetsHelper(int[] nums,List<List<Integer>> result,Deque<Integer> deque,int start) {
if(start==nums.length) {
result.add(new ArrayList(deque));
return;
}
subsetsHelper(nums,result,deque,start+1);
deque.addLast(nums[start]);
subsetsHelper(nums,result,deque,start+1);
deque.removeLast();
}
}
79. 单词搜索
回溯
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(search(board,word,i,j,0,visited)) {
return true;
}
}
}
return false;
}
private boolean search(char[][] board,String word,int i,int j,int idx,boolean[][] visited) {
if(idx==word.length()) return true;
if(i<0||j<0||i>=board.length||j>=board[0].length||
visited[i][j]||
board[i][j]!=word.charAt(idx)) {
return false;
}
visited[i][j] = true;
boolean result = search(board,word,i+1,j,idx+1,visited)||
search(board,word,i,j+1,idx+1,visited)||
search(board,word,i-1,j,idx+1,visited)||
search(board,word,i,j-1,idx+1,visited);
visited[i][j] = false;
return result;
}
}
84. 柱状图中最大的矩形(再看看)
双边扩展-超时
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int left = 0;
int right = 0;
int result = 0;
for(int i=0;i<n;i++) {
left = right = i;
while(left-1>=0&&heights[left-1]>=heights[i]) {
left--;
}
while(right+1<n&&heights[right+1]>=heights[i]) {
right++;
}
result = Math.max(result,heights[i]*(right-left+1));
}
return result;
}
}
前后两个单调栈
我还挺牛逼,这个方法过了,除了效率有点低。
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] result = new int[n];
// 前后两个单调队列
Stack<Integer> lrStack = new Stack<>();
lrStack.add(0);
for(int i=1;i<n;i++) {
if(lrStack.isEmpty()||heights[i]>=heights[lrStack.peek()]) {
lrStack.add(i);
} else {
while(!lrStack.isEmpty()&&heights[lrStack.peek()]>heights[i]) {
int p = lrStack.peek();
result[p] = (i-p)*heights[p];
lrStack.pop();
}
lrStack.add(i);
}
}
if(!lrStack.isEmpty()) {
while(!lrStack.isEmpty()) {
int p = lrStack.peek();
result[p] = (n-p)*heights[p];
lrStack.pop();
}
}
Stack<Integer> rlStack = new Stack<>();
rlStack.add(n-1);
for(int i=n-2;i>=0;i--) {
if(rlStack.isEmpty()||heights[i]>=heights[rlStack.peek()]) {
rlStack.add(i);
} else {
while(!rlStack.isEmpty()&&heights[rlStack.peek()]>heights[i]) {
int p = rlStack.peek();
result[p] += (p-i)*heights[p];
rlStack.pop();
}
rlStack.add(i);
}
}
if(!rlStack.isEmpty()) {
while(!rlStack.isEmpty()) {
int p = rlStack.peek();
result[p] += (p+1)*heights[p];
rlStack.pop();
}
}
int res = 0;
for(int i =0;i<n;i++) {
res = Math.max(res,result[i]-heights[i]);
}
return res;
}
}
一个单调栈
两个单调栈复杂了,一个就可以了。注意单调栈第一个可以算到最开始位置,其他都会被peek拦住。
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int result = 0;
Stack<Integer> lrStack = new Stack<>();
for(int i=0;i<n;i++) {
while(!lrStack.isEmpty()&&heights[lrStack.peek()]>heights[i]) {
int p = lrStack.pop();
result = Math.max(result,lrStack.isEmpty()?i*heights[p]:(i-lrStack.peek()-1)*heights[p]);
}
lrStack.add(i);
}
if(!lrStack.isEmpty()) {
while(!lrStack.isEmpty()) {
int p = lrStack.pop();
result = Math.max(result,lrStack.isEmpty()?n*heights[p]:(n-lrStack.peek()-1)*heights[p]);
}
}
return result;
}
}
奇怪,为啥效率这么低。
不改算法,只是Stack
换成Deque
就快了很多:
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int result = 0;
Deque<Integer> lrStack = new LinkedList<>();
for(int i=0;i<n;i++) {
while(!lrStack.isEmpty()&&heights[lrStack.peekLast()]>heights[i]) {
int p = lrStack.pollLast();
result = Math.max(result,lrStack.isEmpty()?i*heights[p]:(i-lrStack.peekLast()-1)*heights[p]);
}
lrStack.addLast(i);
}
if(!lrStack.isEmpty()) {
while(!lrStack.isEmpty()) {
int p = lrStack.pollLast();
result = Math.max(result,lrStack.isEmpty()?n*heights[p]:(n-lrStack.peekLast()-1)*heights[p]);
}
}
return result;
}
}
原因
Stack
继承自Vector
,Vector
很多方法用synchronized
保证线程安全,效率不大行。