NC刷题笔记4-栈
NC14 按之字形顺序打印二叉树
输入：
二叉树
1
2 3
4 5
输出：
[[1],
[3,2],
[4,5]]
思路1:
1 双端队列，用于存放二叉树结点信息
2 用链表存储每层的信息，奇数从左到右，偶数从右向左
import java.util. ;
/
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/
public class Solution {
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
if(pRoot==null) return res;
queue.add(pRoot);
int index=0;
while(!queue.isEmpty()){
int n=queue.size();
LinkedList<Integer> temp=new LinkedList<>();
index++;
for(int i=0;i<n;i++){
TreeNode node=queue.poll();
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
if(index%2==1){
temp.addLast(node.val);
}else{
temp.addFirst(node.val);
}
}
res.add(new ArrayList<>(temp));
}
return res;
}
}
NC45 实现二叉树先序，中序和后序遍历
描述
给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。
数据范围：0≤n≤1000，树上每个节点的val值满足0≤val≤100
要求：空间复杂度 O(n)，时间复杂度 O(n)
示例1
输入：{1,2,3}
返回值：[[1,2,3],[2,1,3],[2,3,1]]
示例2
输入：{}
返回值：[[],[],[]]
思路1：递归写法
根左右
左根右
左右根
思路2：非递归写法
根左右
左根右
左右根
思路1：
import java.util. ;
/
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
}
/
public class Solution {
/
@param root TreeNode类 the root of binary tree
@return int整型二维数组
/
public int[][] threeOrders (TreeNode root) {
// write code here
ArrayList<Integer> res1=new ArrayList<>();
ArrayList<Integer> res2=new ArrayList<>();
ArrayList<Integer> res3=new ArrayList<>();
preOrder(root,res1);
inOrder(root,res2);
postOrder(root,res3);
return fillArray(res1,res2,res3);
}
public void preOrder(TreeNode root,ArrayList<Integer> res){
if(root==null) return;
res.add(root.val);
if(root.left!=null) preOrder(root.left,res);
if(root.right!=null) preOrder(root.right,res);
}
public void inOrder(TreeNode root,ArrayList<Integer> res){
if(root==null) return;
if(root.left!=null) inOrder(root.left,res);
res.add(root.val);
if(root.right!=null) inOrder(root.right,res);
}
public void postOrder(TreeNode root,ArrayList<Integer> res){
if(root==null) return;
if(root.left!=null) postOrder(root.left,res);
if(root.right!=null) postOrder(root.right,res);
res.add(root.val);
}
public int[][] fillArray(ArrayList<Integer> res1,ArrayList<Integer> res2,ArrayList<Integer> res3){
int[][] res=new int[3][res1.size()];
for(int i=0;i<res1.size();i++){
res[0][i]=res1.get(i);
res[1][i]=res2.get(i);
res[2][i]=res3.get(i);
}
return res;
}
}
思路2：
import java.util. ;
public class Solution {
public int[][] threeOrders (TreeNode root) {
ArrayList<Integer> res1=new ArrayList<>();
ArrayList<Integer> res2=new ArrayList<>();
ArrayList<Integer> res3=new ArrayList<>();
preOrder(root,res1);
inOrder(root,res2);
postOrder(root,res3);
return fillArray(res1,res2,res3);
}
public void preOrder(TreeNode root, ArrayList<Integer> list) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
list.add(curr.val);
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
}
}
public void inOrder(TreeNode root, ArrayList<Integer> list) {
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (!stack.isEmpty() || curr != null) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
curr = stack.pop();
list.add(curr.val);
curr = curr.right;
}
}
}
public void postOrder(TreeNode root, ArrayList<Integer> list) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
list.add(0, curr.val);
if(curr.left != null) {
stack.push(curr.left);
}
if(curr.right != null) {
stack.push(curr.right);
}
}
}
public int[][] fillArray(ArrayList<Integer> res1,ArrayList<Integer> res2,ArrayList<Integer> res3){
int[][] res=new int[3][res1.size()];
for(int i=0;i<res1.size();i++){
res[0][i]=res1.get(i);
res[1][i]=res2.get(i);
res[2][i]=res3.get(i);
}
return res;
}
}
NC52 有效括号序列
描述
给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
数据范围：字符串长度0≤n≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)
示例1
输入："["
返回值：false
示例2
输入："[]"
返回值：true
思路1：
模拟栈，最后stack为空就是有效，不为空就是无效
思路2：
模拟栈，放入的时候不匹配就直接返回false
思路1：
import java.util. ;
public class Solution {
public boolean isValid (String s) {
// write code here
Stack<Character> stack=new Stack<>();
char[] chars=s.toCharArray();
for(int i=0;i<chars.length;i++){
char c=chars[i];
if(c==']'&&!stack.isEmpty()&&stack.peek()=='['){
stack.pop();
}else if(c==')'&&!stack.isEmpty()&&stack.peek()=='('){
stack.pop();
}else if(c=='}'&&!stack.isEmpty()&&stack.peek()=='{'){
stack.pop();
}else{
stack.push(c);
}
}
return stack.isEmpty()?true:false;
}
}
思路2：
import java.util. ;
public class Solution {
public boolean isValid (String s) {
// write code here
Stack<Character> stack=new Stack<Character>();
char[] chars=s.toCharArray();
for(int i=0;i<chars.length;i++){
char c=chars[i];
if(c=='('||c=='['||c=='{'){
stack.push(c);
}else if(c==')'){
if(stack.isEmpty()) return false;
if(stack.peek()!='(') return false;
stack.pop();
}else if(c==']'){
if(stack.isEmpty()) return false;
if(stack.peek()!='[') return false;
stack.pop();
}else if(c=='}'){
if(stack.isEmpty()) return false;
if(stack.peek()!='{') return false;
stack.pop();
}
}
return stack.isEmpty();
}
}
NC76 用两个栈实现队列
思路1：
一个栈负责进，一个栈负责出
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(!stack2.isEmpty()){
return stack2.pop();
}else{
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
}
LC84 直方图最大矩阵
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积
例1：
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
例2：
输入： heights = [2,4]
输出： 4
思路：
单调栈，找到左右比自己小的索引
1 维护一个从小到大的单调栈
2 新建数组长度比原来数组长度多2
3 遍历新数组，开始单调栈构建，每碰到逆序的时候，弹出元素，弹出的元素作为高度，stack的顶部为左端，i为右端，计算一下面积，
class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0;
Deque<Integer> stack = new ArrayDeque<>();
int[] new_heights = new int[heights.length + 2];
for (int i = 1; i < heights.length + 1; i++) {
new_heights[i] = heights[i - 1];
}
for (int i = 0; i < new_heights.length; i++) {
while (!stack.isEmpty() && new_heights[stack.peek()] > new_heights[i]) {
int cur = stack.pop();
int l = stack.peek();
int r = i;
res = Math.max(res, (r - l - 1) new_heights[cur]);
}
stack.push(i);
}
return res;
}
}
NC90 包含min函数的栈
描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
数据范围：操作数量满足0≤n≤300 ，输入的元素满足∣val∣≤10000
进阶：栈的各个操作的时间复杂度是O(1) ，空间复杂度是O(n)
示例:
输入: ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
输出: -1,2,1,-1
解析:
"PSH-1"表示将-1压入栈中，栈中元素为-1
"PSH2"表示将2压入栈中，栈中元素为2，-1
“MIN”表示获取此时栈中最小元素==>返回-1
"TOP"表示获取栈顶元素==>返回2
"POP"表示弹出栈顶元素，弹出2，栈中元素为-1
"PSH1"表示将1压入栈中，栈中元素为1，-1
"TOP"表示获取栈顶元素==>返回1
“MIN”表示获取此时栈中最小元素==>返回-1
示例1
输入：["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
返回值：-1,2,1,-1
思路：
维护两个栈，一个保存出入栈的顺序，一个保存最小元素
最小栈：
入栈：为空 或者 小于等于栈顶元素
出栈：pop元素等于栈顶就pop
import java.util.Stack;
public class Solution {
Stack<Integer> minstack=new Stack<>();
Stack<Integer> stack=new Stack<>();
public void push(int node) {
stack.push(node);
if(minstack.isEmpty()||(!minstack.isEmpty()&&minstack.peek()>=node)){
minstack.push(node);
}
}
public void pop() {
int n=stack.pop();
if(minstack.peek()==n){
minstack.pop();
}
}
public int top() {
return stack.peek();
}
public int min() {
return minstack.peek();
}
}
NC115 栈和排序
描述
给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈
你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列
排列：指 1 到 n 每个数字出现且仅出现一次
数据范围：1≤n≤5×10^4，排列中的值都满足1≤val≤n
进阶：空间复杂度 O(n) ，时间复杂度 O(n)
示例1
输入：[2,1,5,3,4]
返回值：[5,4,3,1,2]
说明：
操作 栈 结果
2 入栈；[2] []
1 入栈；[2\1] []
5 入栈；[2\1\5] []
5 出栈；[2\1] [5]
3 入栈；[2\1\3] [5]
4 入栈；[2\1\3\4] [5]
4 出栈；[2\1\3] [5,4]
3 出栈；[2\1] [5,4,3]
1 出栈；[2] [5,4,3,1]
2 出栈；[] [5,4,3,1,2]
示例2
输入：[1,2,3,4,5]
返回值：[5,4,3,2,1]
思路：
需要一个标记数组，因为元素是1-n，所以第一个出栈的就是n
1 需要一个栈、一个标记数组
2 入栈并标记 到n的第一个出栈
3 比较栈顶元素和为入栈元素的最大值，谁大弹谁
import java.util. ;
public class Solution {
public int[] solve (int[] a) {
Stack<Integer> stack=new Stack<>();
int n=a.length;
boolean[] status=new boolean[n+1];
int[] res=new int[n];
int count=0;
for(int i=0;i<a.length;i++){
stack.push(a[i]);
status[a[i]]=true;
while(n>0 &&status[n]){
n--;
}
while(!stack.isEmpty() && n<=stack.peek()){
res[count++]=stack.pop();
}
}
while(!stack.isEmpty()){
res[count++]=stack.pop();
}
return res;
}
}
NC117 直方图最大矩阵
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积
例1：
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
例2：
输入： heights = [2,4]
输出： 4
思路：
单调栈，找到左右比自己小的索引
1 维护一个从小到大的单调栈
2 新建数组长度比原来数组长度多2
3 遍历新数组，开始单调栈构建，每碰到逆序的时候，弹出元素，弹出的元素作为高度，stack的顶部为左端，i为右端，计算一下面积，
class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0;
Deque<Integer> stack = new ArrayDeque<>();
int[] new_heights = new int[heights.length + 2];
for (int i = 1; i < heights.length + 1; i++) {
new_heights[i] = heights[i - 1];
}
for (int i = 0; i < new_heights.length; i++) {
while (!stack.isEmpty() && new_heights[stack.peek()] > new_heights[i]) {
int cur = stack.pop();
int l = stack.peek();
int r = i;
res = Math.max(res, (r - l - 1) new_heights[cur]);
}
stack.push(i);
}
return res;
}
}
NC137 表达式求值
描述
请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：0≤∣s∣≤100，保证计算结果始终在整型范围内
要求：空间复杂度：O(n)，时间复杂度O(n)
示例1
输入："1+2"
返回值：3
示例2
输入："(2 (3-4)) 5"
返回值：-10
示例3
输入："3+2 3 4-1"
返回值：26
思路：
双栈（为了避免负数开头，数字栈中压入0）
1 （和 直接入栈
2 数字获取整个数字入栈
3 +、-进行上一步的计算
4 ）把最近的括号计算完
5 遍历完开始最后的合并计算，直到操作符栈为空
import java.util.Stack;
/
@Author 丁永新
@Date 2022/1/23
/
public class Solution {
public int solve (String s) {
s=s.replaceAll(" ","");//替换空格
char[] chars=s.toCharArray();
Stack<Integer> numops=new Stack<>();
numops.add(0);//防止出现负数为第一个数字
Stack<Character> signops=new Stack<>();
for(int i=0;i<chars.length;i++){
char c=chars[i];
if(c=='('||c==' '||c=='/'){
signops.push(c);
}else if(isNum(c)){
String temp="";
while(i<chars.length&&isNum(chars[i])){
temp+=chars[i];
i++;
}
i--;
numops.push(Integer.parseInt(temp));
}else if(c=='+'||c=='-'){
while(!numops.isEmpty()&&!signops.isEmpty()
&&(signops.peek()=='+'||signops.peek()=='-'||signops.peek()==' '||signops.peek()=='/')){
int n1=numops.pop();
int n2=numops.pop();
char sig=signops.pop();
numops.push(calculation(n2,n1,sig));
}
signops.push(c);
}else if(c==')'){
while(!numops.isEmpty()&&signops.peek()!='('){
int n1=numops.pop();
int n2=numops.pop();
char sig=signops.pop();
numops.push(calculation(n2,n1,sig));
}
signops.pop();
}
}
while(!signops.isEmpty()){
int n1=numops.pop();
int n2=numops.pop();
char sig=signops.pop();
numops.push(calculation(n2,n1,sig));
}
return numops.peek();
}
public int calculation(int a,int b,char sign){
switch(sign){
case '+':return a+b;
case '-':return a-b;
case ' ':return a b;
case '/':return (int)(a/b);
default :return 0;
}
}
public boolean isNum(char c){
if(c>='0'&&c<='9') return true;
return false;
}
}
NC 157单调栈
描述
给定一个长度为 n 的可能含有重复值的数组 arr ，找到每一个 i 位置左边和右边离 i 位置最近且值比 arri 小的位置。
请设计算法，返回一个二维数组，表示所有位置相应的信息。位置信息包括：两个数字 l 和 r，如果不存在，则值为 -1，下标从 0 开始。
数据范围：1≤n≤10^5 ，-10^9≤arr[i]≤10^9
进阶：空间复杂度 O(n) ，时间复杂度 O(n)
示例1
输入：[3,4,1,5,6,2,7]
返回值：[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]
示例2
输入：[1,1,1,1]
返回值：[[-1,-1],[-1,-1],[-1,-1],[-1,-1]]
思路1：
暴力解法：寻找位置index左右两侧第一个比index处小的索引
思路2：
单调栈:单调栈一般用于求左右两边比当前值小或大的数据结构
求左侧：
[3,4,1,5,6,2,7]
num=3 栈为空 -1 入栈 单调栈：0
num=4 大于栈顶 0 符合 入栈 单调栈：0 1
num=1 小于栈顶 -1 弹出所有 入栈 单调栈 2
num=5 大于栈顶 2 符合 入栈 单调栈 2 3
num=6 大于栈顶 3 符合 入栈 单调栈 2 3 4
num=2 小于栈顶 2 不符合 弹出 3 4 入栈 单调栈 2 5
num=7 大于栈顶 5 符合 入栈 单调栈 2 5 6
左侧结果：-1 0 -1 2 3 2 5
右侧结果：2 2 -1 5 5 -1 -1
思路1：
import java.util. ;
public class Solution {
public int[][] foundMonotoneStack (int[] nums) {
// write code here
int len = nums.length;
int ans[][] = new int[len][2];
for(int i=0;i<len;i++){
int l=-1,r=-1;
for(int j=i-1;j>=0;j--){
if(nums[j]<nums[i]){
l = j;
break;
}
}
for(int k=i+1;k<len;k++){
if(nums[k]<nums[i]){
r = k;
break;
}
}
ans[i][0] = l;
ans[i][1] = r;
}
return ans;
}
}
思路2：
import java.util. ;
public class Solution {
public int[][] foundMonotoneStack (int[] nums) {
Stack<Integer> stack=new Stack<>();
int[][] ans=new int[nums.length][2];
//左侧单调栈
for(int i=0;i<nums.length;i++){
while(!stack.isEmpty()&&nums[stack.peek()]>=nums[i]){
stack.pop();
}
if(stack.isEmpty()){
ans[i][0]=-1;
}else{
ans[i][0]=stack.peek();
}
stack.push(i);
}
//右侧单调栈
stack.clear();
for(int i=nums.length-1;i>=0;i--){
while(!stack.isEmpty()&&nums[stack.peek()]>=nums[i]){
stack.pop();
}
if(stack.isEmpty()){
ans[i][1]=-1;
}else{
ans[i][1]=stack.peek();
}
stack.push(i);
}
return ans;
}
}
NC175 合法括号字符串
描述
给定一个字符串s，字符串s只包含以下三种字符: (， ，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
1.左括号'('必须有对应的右括号')'
2.右括号')'必须有对应的左括号'('
3.左括号必须在对应的右括号前面
4. 可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符
5.空字符串也视为合法的括号字符串
数据范围: 1<=s.length<=100
示例1 输入："()()" 返回值：true
示例2 输入："(( )" 返回值：true
示例3 输入："( )" 返回值：true
思路1：
模拟栈
双栈 left star
1 记录左括号下标和星号下表
2 左括号、星号直接入栈
3 右括号开始消去，优先消除左括号，在消除 号
4 最后判断剩下的左括号和星号是否匹配
思路2：
贪心算法：左括号最小应该消除几个能不能消完 右括号最小应该消除几个能不能消完
思路1：
import java.util. ;
public class Solution {
/
代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
@param s string字符串
@return bool布尔型
/
public boolean isValidString (String s) {
//新建两个栈left、star，分别记录未匹配的左括号和 号对应下标
LinkedList<Integer> left=new LinkedList<>();
LinkedList<Integer> star=new LinkedList<>();
int n=s.length();
for(int i=0;i<n;i++){
char c=s.charAt(i);
//左括号下标入栈
if(c=='('){
left.push(i);
}
// 号下标入栈
else if(c==' '){
star.push(i);
}
//如果是右括号
else{
//首先匹配左括号
if(!left.isEmpty()){
left.pop();
}
//其次匹配 号
else if(!star.isEmpty()){
star.pop();
}
//如果都没有，说明有右括号找不到匹配对象
else{
return false;
}
}
}
//检查未匹配的左括号和 号
while(!left.isEmpty()&&!star.isEmpty()){
int top1=left.pop();
int top2=star.pop();
//每一个左括号都必须有一个 号（视为右括号）与之匹配
if(top1>top2){
return false;
}
}
return left.isEmpty();
}
}
思路2：
import java.util. ;
public class Solution {
public boolean isValidString (String s) {
int cnt=0;int n=s.length();
for(int i=0;i<n;i++){
if(s.charAt(i)==')'){
if(cnt<1) return false;
cnt--;
}else{
cnt++;
}
}
cnt=0;
for(int i=n-1;i>=0;i--){
if(s.charAt(i)=='('){
if(cnt<1) return false;
cnt--;
}else{
cnt++;
}
}
return true;
}
}
NC199 字符串解码
描述
给一个加密过的字符串解码，返回解码后的字符串。
加密方法是：k[c] ，表示中括号中的 c 字符串重复 k 次，例如 3[a] 解码结果是 aaa ，保证输入字符串符合规则。不会出现类似 3a , 3[3] 这样的输入。
数据范围：输出的字符串长度满足1≤n≤50
示例1
输入："3[a]"
返回值："aaa"
示例2
输入："abc"
返回值："abc"
示例3
输入："3[3[b]]"
返回值："bbbbbbbbb"
思路1：
栈
思路2：
递归法
NC208 每日温度
描述
根据往后 n 天的天气预报，计算每一天需要等待几天才会出现一次更高的气温，如果往后都没有更高的气温，则用 0 补位。
例如往后三天的气温是 [1,2,3] ， 则输出 [1,1,0]
数据范围：1≤n≤10^5，每天的温度满足0≤temp≤100
示例1
输入：[1,2,3]
返回值：[1,1,0]
示例2
输入：[2,4,5,9,10,0,9]
返回值：[1,1,1,1,0,1,0]
示例3
输入：[3,1,4]
返回值：[2,1,0]
思路：
单调栈
import java.util. ;
public class Solution {
public int[] temperatures (int[] temperatures) {
Stack<Integer> stack=new Stack<>();
int n=temperatures.length;
if(n==1) return new int[]{0};
int[] res=new int[n];
for(int i=n-1;i>=0;i--){
if(stack.isEmpty()){
res[i]=0;
stack.push(i);
}else{
while(!stack.isEmpty() &&temperatures[i]>=temperatures[stack.peek()]){
stack.pop();
}
if(stack.isEmpty()){
res[i]=0;
}else{
res[i]=stack.peek()-i;
}
stack.push(i);
}
}
return res;
}
}
NC 216 逆波兰表达式
描述
给定一个逆波兰表达式，求表达式的值。
数据范围：表达式长度满足1≤n≤10^4，表达式中仅包含数字和 + ，- , , / ，其中数字的大小满足∣val∣≤200 。
示例1 输入：["2","1","+","4"," "] 返回值：12
示例2 输入：["2","0","+"] 返回值：2
思路： 栈
遇见数字直接压栈
遇见符号直接计算
import java.util. ;
public class Solution {
public int evalRPN (String[] tokens) {
Stack<String> stack=new Stack<>();
for(int i=0;i<tokens.length;i++){
if(isSign(tokens[i])){
int n1=Integer.parseInt(stack.pop());
int n2=Integer.parseInt(stack.pop());
if(tokens[i].equals("+")){
stack.push(n1+n2+"");
}else if(tokens[i].equals("-")){
stack.push(n2-n1+"");
}else if(tokens[i].equals(" ")){
stack.push(n1 n2+"");
}else if(tokens[i].equals("/")){
stack.push((int)(n2/n1)+"");
}
}else{
stack.push(tokens[i]);
}
}
return Integer.parseInt(stack.pop());
}
public boolean isSign(String str){
return str.equals("+")||str.equals("-")||str.equals(" ")||str.equals("/");
}
}
NC219 移掉 K 位数字
描述
给定一个以字符串表示的数字 num 和一个数字 k ，从 num 中移除 k 位数字，使得剩下的数字最小。如果可以删除全部数字则剩下 0
数据范围：num的长度满足1≤k≤n≤10^5，保证 num 中仅包含 0~9 的十进制数
示例1
输入：
"1432219",3
返回值："1219"
说明：
移除 4 3 2 后剩下 1219
示例2
输入："10",1
返回值："0"
思路：
首要目的是删除高位的大数（数组中排在索引小的位置），才能使得数字尽可能小。那么我们可以维持一个从栈底到栈顶单调不减的单调栈，在从高位向低位遍历num的各位数字时，不断检查栈中元素的单调性。
一旦这个单调性被破坏，就表示高位数大，低位数小，这时候如果还剩下删除操作，就将栈顶元素弹出再把当前元素压栈（相当于移掉一个数）；满足单调不减就直接把当前数字压栈。
经过上面的过程遍历完数组后还有一点需要注意：就是需要去除结果数字的前导零。这样得到的才是一个合法的数字。
1 单调栈弹出k个数字
2 弹出所有并反转
3 去掉头部的0
import java.util. ;
public class Solution {
public String removeKnums (String num, int k) {
// write code here
Stack<Character> stack=new Stack<>();
for(int i=0;i<num.length();i++){
while(k>0&&!stack.isEmpty()&&stack.peek()>num.charAt(i)){
stack.pop();
k--;
}
stack.push(num.charAt(i));
}
StringBuilder sb=new StringBuilder();
while(!stack.isEmpty()) sb.append(stack.pop());
sb=sb.reverse();
String res= sb.toString();
//把头部的0都抛出
for(int i=0;i<res.length();i++){
if(res.charAt(i)!='0'){
return res.substring(i,res.length()).equals("")?"0":res.substring(i,res.length());
}
}
return res;
}
}
NC237 最大矩形
描述
给定一个仅包含 0 和 1 ，大小为 n m 的二维二进制矩阵，找出仅包含 1 的最大矩形并返回面积。
数据范围：1≤n,m≤200 保证输入的矩形中仅含有 0 和 1
例如输入[[1,0,1,0,0],[1,1,1,1,0],[1,1,1,1,1],[1,0,0,1,0]]时，对应的输出为8，所形成的最大矩形如下图所示：
示例1
输入：[[1]]
返回值：1
示例2
输入：[[1,1],[0,1]]
返回值：2
示例3
输入：[[0,0],[0,0]]
返回值：0
示例4
输入：[[1,0,1,0,0],[1,1,1,1,0],[1,1,1,1,1],[1,0,0,1,0]]
返回值：8
思路：
和直方图最大面积类似，先求出来每个位置在纵向的连续的1的个数，包括自己
例子：
[[1,0,1,0,0],
[1,1,1,1,0],
[1,1,1,1,1],
[1,0,0,1,0]]
step 1 求纵向连续1的个数
[1,0,1,0,0],
[2,1,2,1,0],
[3,2,3,2,1],
[4,0,0,3,0]
step 2 单调栈 求每一行的最大矩形面积
import java.util. ;
public class Solution {
public int maximalRectangle (int[][] matrix) {
int res=0;
//遍历每一行
for(int i=0;i<matrix.length;i++){
//构造这一行的直方图
int[] temp=new int[matrix[i].length];
for(int j=0;j<matrix[i].length;j++){
//某个位置为1
if(matrix[i][j]==1){
//开始向上寻找连续的1的个数
int index=i,n=0;
while(index>=0&&matrix[index][j]==1){
n++;
index--;
}
temp[j]=n;
}
}
res=Math.max(res,largestRectangleArea(temp));
}
return res;
}
//直方图最大面积
public int largestRectangleArea(int[] heights) {
int res=0;
int[] newheights=new int[heights.length+2];
for(int i=0;i<heights.length;i++){
newheights[i+1]=heights[i];
}
Stack<Integer> stack=new Stack<>();
for(int i=0;i<newheights.length;i++){
while(!stack.isEmpty()&&newheights[stack.peek()]>newheights[i]){
int cur=stack.pop();
int l=stack.peek();
int r=i;
res=Math.max(res,(r-l-1) newheights[cur]);
}
stack.push(i);
}
return res;
}
}
NC240 计算器（一）
描述
给定一个字符串形式的表达式 s ，请你实现一个计算器并返回结果。
数据范围：表达式长度满足1≤∣s∣≤10^5，字符串中包含 + , - , ( , ) ，保证表达式合法。
示例1 输入："1+2" 返回值：3
示例2 输入："1-1" 返回值：0
示例3 输入："-0" 返回值：0
思路：和NC137一样
import java.util. ;
public class Solution {
public int calculate (String s) {
s=s.replaceAll(" ","");//替换空格
char[] chars=s.toCharArray();
Stack<Integer> numops=new Stack<>();
numops.add(0);//防止出现负数为第一个数字
Stack<Character> signops=new Stack<>();
for(int i=0;i<chars.length;i++){
char c=chars[i];
if(c=='('||c==' '||c=='/'){
signops.push(c);
}else if(isNum(c)){
String temp="";
while(i<chars.length&&isNum(chars[i])){
temp+=chars[i];
i++;
}
i--;
numops.push(Integer.parseInt(temp));
}else if(c=='+'||c=='-'){
while(!numops.isEmpty()&&!signops.isEmpty()
&&(signops.peek()=='+'||signops.peek()=='-'||signops.peek()==' '||signops.peek()=='/')){
int n1=numops.pop();
int n2=numops.pop();
char sig=signops.pop();
numops.push(calculation(n2,n1,sig));
}
signops.push(c);
}else if(c==')'){
while(!numops.isEmpty()&&signops.peek()!='('){
int n1=numops.pop();
int n2=numops.pop();
char sig=signops.pop();
numops.push(calculation(n2,n1,sig));
}
signops.pop();
}
}
while(!signops.isEmpty()){
int n1=numops.pop();
int n2=numops.pop();
char sig=signops.pop();
numops.push(calculation(n2,n1,sig));
}
return numops.peek();
}
public int calculation(int a,int b,char sign){
switch(sign){
case '+':return a+b;
case '-':return a-b;
case ' ':return a b;
case '/':return (int)(a/b);
default :return 0;
}
}
public boolean isNum(char c){
if(c>='0'&&c<='9') return true;
return false;
}
}
NC241 计算器（二）
描述
给定一个字符串形式的表达式 s ，请你实现一个计算器并返回结果，除法向下取整。
数据范围：表达式长度满足1≤∣s∣≤10^5，字符串中包含 + , - , , / , 保证表达式合法。
示例1
输入："1 10"
返回值：10
示例2
输入："8 9-19"
返回值：53
示例3
输入："100000 100 0"
返回值：0
示例4
输入："100000 100/9"
返回值：1111111
思路：双栈
1 符号 直接入栈
2 数字 判断符号栈是否为空
空 ：直接入栈
不为空：计算后入栈
import java.util. ;
public class Solution {
public int calculate (String s) {
s=s.replaceAll(" ","");//替换空格
char[] chars=s.toCharArray();
Stack<Integer> numops=new Stack<>();
numops.add(0);//防止出现负数为第一个数字
Stack<Character> signops=new Stack<>();
for(int i=0;i<chars.length;i++){
char c=chars[i];
if(isNum(c)){
//是数字
String temp="";
while(i<chars.length&&isNum(chars[i])){
temp+=chars[i];
i++;
}
i--;
int n=Integer.parseInt(temp);
//入栈
if(!signops.isEmpty()){
char ss=signops.pop();
switch(ss){
case '+': numops.push(n);break;
case '-': numops.push(-n);break;
case ' ': numops.push(numops.pop() n);break;
case '/': numops.push((int)(numops.pop()/n));break;
default:;
}
}else{
numops.push(n);
}
}else{ //不是数字
signops.push(c);
}
}
while(numops.size()!=1){
int n1=numops.pop();
int n2=numops.pop();
numops.push(n1+n2);
}
return numops.peek();
}
public boolean isNum(char c){
if(c>='0'&&c<='9') return true;
return false;
}
}
版权声明：本文为qq_34329430原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。