The stack
A monotonic stack is a stack whose elements must be in ascending or descending order. Stacks in ascending order are called increasing stacks, and stacks in descending order are called decreasing stacks.
Valid string
-
There are only characters ‘(‘ and ‘)’ in the string. Valid strings require parentheses to pair.
For example: Input: “()” output: true
Explanation :(), ()(), (()) are legal. ()()()() is illegal.
boolean isValid(String s);
/** * The string contains only characters '(' and ')'. Valid strings require parentheses to pair. For example: Input: "()" Output: true * Explanation: (), ()(), (()) are legal. ()()()() is illegal. * Time complexity O(n) Space complexity O(n) */
private static boolean isValid(String s) {
if (null == s || s.length() == 0 || s.length() % 2! =0) {
return false;
}
Stack<Character> stack = new Stack<Character>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (stack.isEmpty()) {
stack.push(chars[i]);
continue;
}
if ('(' == stack.peek() && ') ' == chars[i]) {
stack.pop();
} else{ stack.push(chars[i]); }}return stack.isEmpty();
}
Copy the codeOptimization: the data is pushed (, the elements in the stack are the same, there is no need to use the stack, just the number of elements in the stack.
/** * Time complexity O(N) Space complexity O(1) */
private static boolean isValid1(String s) {
if (null == s || s.length() == 0 || s.length() % 2! =0) {
return false;
}
char[] chars = s.toCharArray();
int num = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
num++;
} else {
if (num <= 0) {
return false; } num--; }}return num == 0;
}
Copy the codeVariant: given a include only ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘string, to determine whether a string is effective. A valid string must meet the following requirements:
- An open parenthesis must be closed with a close parenthesis of the same type
- The left parentheses must be closed in the correct order
- Note that an empty string can be considered a valid string
private static boolean isValidC(String s) {
if (null == s || s.length() == 0 || s.length() % 2! =0) {
return false;
}
Stack<Character> stack = new Stack<Character>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (' ' == chars[i]) {
return false;
}
if ('(' == chars[i] || '{' == chars[i] || '[' == chars[i]) {
stack.push(chars[i]);
continue;
}
if (stack.isEmpty()) {
return false;
}
if (') ' == chars[i]) {
if ('(' == stack.peek()) {
stack.pop();
} else {
return false; }}if ('} ' == chars[i]) {
if ('{' == stack.peek()) {
stack.pop();
} else {
return false; }}if ('] ' == chars[i]) {
if ('[' == stack.peek()) {
stack.pop();
} else {
return false; }}}return stack.isEmpty();
}
Copy the code-
There are a lot of fish in the water, and you can think of them as sitting on the X-axis. Given two arrays Size, Dir, Size[I] denotes the Size of the ith fish, Dir[I] denotes the direction of the fish (0 indicates left, 1 indicates right). The two arrays represent the size and direction of the fish, respectively, and the two arrays are of equal length. The behavior of fish meets the following criteria:
- All the fish start swimming at the same time, one unit at a time in the direction of the fish.
- When facing each other, bigger fish eat smaller ones;
- Fish are all different sizes.
Enter: Size = [4, 2, 5, 3, 1], Dir = [1, 1, 0, 0, 0]
Output: 3
int solution(int[] size, int[] dir)
/** * Time complexity O(n) Space complexity O(n) */
private static int solution(int[] size, int[] dir) {
if (size.length <= 1 || dir.length <= 1|| size.length ! = dir.length) {return size.length;
}
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < size.length; i++) {
boolean hasEat = false;
while(! stack.isEmpty() && dir[stack.peek()] ==1 && dir[i] == 0) {
if (size[stack.peek()] > size[i]) {
hasEat = false;
break;
}
stack.pop();
}
if (!hasEat) {
stack.push(i);
}
}
return stack.size();
}
Copy the code-
An array of integers, A, finds each element: the first subscript position on the right that is smaller than me, or -1 if not.
Input: [5, 2]
Output: [1, -1]
int[] findRightSmall(int[] arr)
/** * a number always wants to match the number to the left that is larger than it. When a match is made, the smaller number cancels out the larger number. * * Time complexity O(N) space f again O(N) * the position of the first element on the right of the array smaller than me, solved using the increment stack. * * /
private static int[] findRightSmall(int[] arr) {
int[] resultArr = new int[arr.length];
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < arr.length; i++) {
while(! stack.isEmpty() && arr[stack.peek()] > arr[i]){ resultArr[stack.pop()] = i; } stack.push(i); }while(! stack.isEmpty()){ resultArr[stack.pop()] =-1;
}
return resultArr;
}
Copy the code-
Given an array of positive integers and k, it is required to extract k numbers in turn and output a subsequence of the array. The following requirements are met: 1. Length k; 2. Minimum dictionary order.
Input: nums = [3,5,2,6], k = 2
Output: [2, 6]
private static int[] findSmallSeq(int[] arr, int k){
int[] result = new int[k];
Stack<Integer> stack = new Stack<Integer>();
for(int i=0; i<arr.length; i++){
int leftNum = arr.length - i;
while( !stack.empty() && stack.size()+ leftNum > k && stack.peek()> arr[i]){
stack.pop();
}
stack.push(arr[i]);
}
while(stack.size() > k){
stack.pop();
}
for(int i=k-1; i>=0; i--){
result[i] = stack.peek();
stack.pop();
}
return result;
}
Copy the code-
N non-negative integers are given to represent the heights of the columns in a bar graph. Each column is adjacent to each other and has a width of 1. Find the maximum area of rectangles that can be outlined in the bar chart.
Input:,1,5,6,2,3 [2]
Output: 10
/** * need to find the first number on the left less than A[I], leftPos, also need to find the first number on the right less than A[I]. rightPos */
private static int largestRectangleArea1(int[] arr){
int[] leftSmall = findLeftSmall(arr);
int[] rightSmall = findRightSmall(arr);
int result =0;
for (int i = 0; i < arr.length; i++) {
int leftPos = leftSmall[i];
int rightPos = rightSmall[i] == -1 ? arr.length: rightSmall[i];
int width = rightPos - leftPos -1;
result = Math.max(result, width * arr[i]);
}
return result;
}
/** * query the left less than */
private static int[] findLeftSmall(int [] arr){
int[] resultArr = new int[arr.length];
Stack<Integer> stack = new Stack<Integer>();
for (int i = arr.length-1; i > 0; i--) {
while(! stack.isEmpty() && arr[stack.peek()] > arr[i]){ resultArr[stack.pop()] = i; } stack.push(i); }while(! stack.isEmpty()){ resultArr[stack.pop()] =-1;
}
return resultArr;
}
/** ** Query the number on the right less than */
private static int[] findRightSmall(int[] arr) {
int[] resultArr = new int[arr.length];
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < arr.length; i++) {
while(! stack.isEmpty() && arr[stack.peek()] > arr[i]){ resultArr[stack.pop()] = i; } stack.push(i); }while(! stack.isEmpty()){ resultArr[stack.pop()] =-1;
}
return resultArr;
}
Copy the code public int largestRectangleArea(int[] A) {
final int N = A == null ? 0 : A.length;
int top = 0;
int[] s = new int[N];
int ans = 0;
for (int i = 0; i <= N; i++) {
final int x = i == N ? -1 : A[i];
while (top > 0 && A[s[top - 1]] > x) {
final int height = A[s[--top]];
final int rightPos = i;
final int leftPos = top > 0 ? s[top - 1] : -1;
final int width = rightPos - leftPos - 1;
final int area = height * width;
ans = Math.max(ans, area);
}
s[top++] = i;
}
return ans;
}
Copy the code