-
思路：
-
使用map和stack结合. -
map中的key是右括号，value是左括号。 -
stack中存放所有的左括号
- 扫描到当前字符时，如果map中包含这个key，说明是遇到了右括号。
- 遇见右括号的时候，看栈顶是否和map中key对应的value一样。一样就弹出。方便下一个右括号找匹配的左括号。
- 不一样就false。
- 不是就是遇见左括号，进栈。
-
最后只需要判断栈是否为空即可。
-
代码 class Solution {
public boolean isValid(String s) {
int n = s.length();
if(n % 2 == 1){
return false;
}
Map<Character, Character> map = new HashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{');
Deque<Character> stack = new LinkedList<>();
for(int i = 0; i < n; i++){
char c = s.charAt(i);
if(map.containsKey(c)){
if(stack.isEmpty() || stack.peek() != map.get(c)){
return false;
}else{
stack.pop();
}
}else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
-
思路：
-
设置一个栈，先放入一个-1。保证是一个单调栈（主要是防止当第一个字符是")"进行pop的时候，出现空指针）。 -
依次扫描
- 如果扫描到当前为左括号，那么入栈。
- 如果扫描到当前为右括号，先出栈，所以预先放入一个-1，就是为了防止空指针异常。
- 如果此时栈为空，入栈。
- 如果此时栈中还有元素，那么此时全局变量为res 和 i - stack.peek()的最大值。
-
返回最大值。
-
代码 class Solution {
public int longestValidParentheses(String s) {
int n = s.length();
int res = 0;
Deque<Integer> stack = new LinkedList<>();
stack.push(-1);
for(int i = 0; i < n; i++){
char c = s.charAt(i);
if(c == '('){
stack.push(i);
}else {
stack.pop();
if(stack.isEmpty()){
stack.push(i);
}else {
res = Math.max(res, i - stack.peek());
}
}
}
return res;
}
}
-
思路：
- 设计一个栈，这个栈是一个单调递增的栈。因为是单调栈，所以保存的是下标。
- 因为题目的意思是按照长宽相乘进行解答的。
- 对给定的数组进行扫描
- 使用
while判断，这样一直找到最远的那个墙（可以接雨水的），栈是否为空以及栈顶对应height数组的值是否大于现在扫描的height值。如果当前height值大于栈顶height值，那么说明出现了凹槽了，可以存放雨水。
- 弹出凹槽。
- 如果弹出之后为空，说明左边弹出完了，左边已经没有比现在更高的墙了。那么到此之后进栈顺序又要从当前的位置重新计算。
- 只要没有弹完，那么说明还有一个墙比当前位置高，记录下该墙的下标，即：栈顶。
- 每次弹出求一次宽度：i - left - 1，-1是因为弹出了一个凹槽，因为凹槽的宽度就是需要的宽度。
- 每次弹出计算一次长度：在当前height值和左边墙的height值选取一个最小值，然后再减去弹出的凹槽值，因为凹槽不一定是全没有的，可能是比较短的墙。
- 结果就是不断的进行长宽相乘再叠加。
- 返回值
- 为什么不需要设置-1这些给栈打底？32题打底的前提是可能首先面对的是右括号，所以要先打底一个-1。本题不需要打底是因为弹出的条件是当前height值高于栈顶的值，否则就入栈。潜台词就是：因为存在和栈顶的比较，那么肯定就有入栈的操作。
- 在求高度的时候，是当前墙的高度和左边墙高度的最小值减去凹槽的高度。
-
代码 class Solution {
public int trap(int[] height) {
int n = height.length;
int res = 0;
Deque<Integer> stack = new LinkedList<>();
for(int i = 0; i < n; i++){
while(!stack.isEmpty() && height[i] > height[stack.peek()]){
int top = stack.pop();
if(stack.isEmpty()){
break;
}
int left = stack.peek();
int widthNow = i - stack.peek() - 1;
int heightNow = Math.min(height[i],height[left]) - height[top];
res += widthNow * heightNow;
}
stack.push(i);
}
return res;
}
}
-
思路：
- 维护一个单调的栈，这个题只能是下标。
- 给柱子两边加一个0，为的就是为了维护一个单调性，防止栈空。
- 为什么要给两边加？加最左边是为了单调，那么加在最右边的目的是为了因为题目的弹出策略，只要当当前柱子的高度小于栈顶柱子的高度就弹出，那么加在最右边是为了计算最后一个柱子的高度形成的矩形面积，如果不加的话，那么就会忽略最后一个实际柱子形成的面积。
- 扫描从左到右。
- 只要当前扫描的柱子高度比栈顶的小，那么说明可以构建出一个面积，如果是当前柱子比栈顶的柱子高度还高，那么说明还有可能存在更高的，所以将更高的入栈，此处和42题不同，42题是将矮的入栈。
- 获取左边柱子。
- 高度取左边柱子和当前柱子的最小值。
- 当前的宽度同样和雨水题一样，i - stack.peek() - 1
- 面积就是宽×高和原面积的最大值。
- 返回最大值
-
代码： class Solution {
public int largestRectangleArea(int[] heights) {
int[] temp = new int[heights.length + 2];
System.arraycopy(heights, 0, temp, 1, heights.length);
Deque<Integer> stack = new LinkedList<>();
int res = 0;
for(int i = 0; i < temp.length; i++){
while(!stack.isEmpty() && temp[i] < temp[stack.peek()]){
int left = stack.pop();
int h = temp[left];
int w = i - stack.peek() - 1;
res = Math.max(res, w * h);
}
stack.push(i);
}
return res;
}
}
-
思路：
- 使用上一题的思路
- 把每列的高度求出之后，当前i，j为1就使得高度加1，否则就置0，使用上一题，求出最大矩形。
- 每次只需要比较一下是否是最大值即可。
- 注意空的判断。
-
代码： class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length == 0){
return 0;
}
int[] heights = new int[matrix[0].length];
int maxArea = 0;
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){
if(matrix[i][j] == '1'){
heights[j] += 1;
}else {
heights[j] = 0;
}
}
maxArea = Math.max(maxArea, largestRectangleArea(heights));
}
return maxArea;
}
public int largestRectangleArea(int[] heights){
int[] temp = new int[heights.length + 2];
System.arraycopy(heights, 0 ,temp, 1, heights.length);
Deque<Integer> stack = new LinkedList<>();
int res = 0;
for(int i = 0; i < temp.length; i++){
while(!stack.isEmpty() && temp[i] < temp[stack.peek()]){
int left = stack.pop();
int h = temp[left];
int w = i - stack.peek() - 1;
res = Math.max(res, w * h);
}
stack.push(i);
}
return res;
}
}
-
思路：
- 先明白题目的意思，即：找到中间是无序数组的长度。
- 使用栈，栈保持单调，分别从两个方向进行，从左到右（保持递增）、从右到左（保持递减）。因为单调，所以栈中存的都是数组下标。
- 从左到右的时候，需要找到比栈顶数（前一个数）小的位置，那么，此时left是min(left,stack.pop())，只要是递增，一直入栈就好。
- 从右到左，需要找到比栈顶数（后一个）大的位置，那么此时的right是max(right,stack.pop())，只要是递减的，一直入栈。
- 最后在返回的时候，做判断，如果right>left，那么返回right - left + 1，否则说明就没有找到。所以在初始化的时候，left=n，right=0。
-
代码： class Solution {
public int findUnsortedSubarray(int[] nums) {
Deque<Integer> stack = new LinkedList<>();
int n = nums.length;
int l = n;
int r = 0;
for(int i = 0; i < n; i++){
while(!stack.isEmpty() && nums[i] < nums[stack.peek()]){
int newLeft = stack.pop();
l = Math.min(l, newLeft);
}
stack.push(i);
}
stack.clear();
for(int i = n - 1; i >= 0; i--){
while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
int newRight = stack.pop();
r = Math.max(r, newRight);
}
stack.push(i);
}
if(r > l){
return r - l + 1;
}else {
return 0;
}
}
}
|