leetcode-84-85-94

leetcode84题85题94题:

leetcode84题(柱状图中最大的矩形):

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//第一种解法,分治法,
var largestRectangleArea = function(heights) {
return computeArea(heights,0,heights.length-1);
};
function computeArea(heights,start,end){
if(start>end){
return 0;
}
var minIndex = start;
for(var i=start;i<=end;i++){//先找到最小的元素的位置
if(heights[minIndex]>heights[i]){
minIndex = i;
}
}
return Math.max(heights[minIndex]*(end-start+1),computeArea(heights,start,minIndex-1),computeArea(heights,minIndex+1,end));//最终的输出结果是最小元素乘数组宽度与左边最大矩形面积与右边最大矩形面积的最大值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//第二种解法,借用栈
var largestRectangleArea = function(heights) {
var maxArea = 0;
var stack = [];
for(var i=0;i<heights.length;i++){//这个循环里面,将最终的stack按照从小到大的顺序排列
//如:2 1 5 6 2 3最终的排列顺序是1 1 2 2 2 3
if(stack.length==0||stack[stack.length-1]<=heights[i]){
stack.push(heights[i]);//如果栈空或者当前元素比栈顶元素大,那么直接push进去
}else{//如果栈不空并且当前元素比栈顶元素小,那么需要将栈中比当前元素大的元素设置为当前元素
var count = 0;
while(stack.length!=0&&stack[stack.length-1]>heights[i]){
count++;
maxArea = Math.max(maxArea,stack[stack.length-1]*count);
stack.pop();
}
while(count--){
stack.push(heights[i]);
}
stack.push(heights[i]);
}

}
//将栈中元素从小到大弄好后,计算此时的最大面积与前面最大面积的最大值
var count = 1;
while(stack.length!=0){
maxArea = Math.max(maxArea,stack[stack.length-1]*count);
stack.pop();
count++;
}
return maxArea;
};

leetcode85题(最大矩形):

给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

示例:

示例

解答(需要借助84题的解答):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
var maximalRectangle = function(matrix) {
if(matrix.length==0){
return 0;
}
var maxArea = 0;
var heights = [];//送进计算直方图面积的函数中,作为高度
var row = matrix.length;//行数,表示直方图的个数
var column = matrix[0].length;//列数,每个直方图的直方个数
for(var i=0;i<column;i++){
heights[i]=0;
}
for(var i=0;i<row;i++){
for(var j=0;j<column;j++){
if(matrix[i][j]=='1'){
heights[j]++;
}else{
heights[j]=0;
}
}//此时得到以第i行结尾的直方图的heights
maxArea = Math.max(maxArea,largestRectangleArea(heights));
}
return maxArea;
};

//此处采用的是第84题的第一种方法

//以下代码计算直方图的最大矩形面积,对于该题,我们只需要不停地移动行来形成不同的直方图来不停地计算最大矩形面积
var largestRectangleArea = function(heights) {
return computeArea(heights,0,heights.length-1);
};
function computeArea(heights,start,end){
if(start>end){
return 0;
}
var minIndex = start;
for(var i=start;i<=end;i++){
if(heights[minIndex]>heights[i]){
minIndex = i;
}
}
return Math.max(heights[minIndex]*(end-start+1),computeArea(heights,start,minIndex-1),computeArea(heights,minIndex+1,end));
}

leetcode94题(二叉树的中序遍历):

给定一个二叉树,返回它的中序 遍历。

示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//解法1:递归解法,简单易懂
var inorderTraversal = function(root) {
var resultArr = [];
function inorderTraversal(root){
if(root==null){
return;
}
inorderTraversal(root.left);
resultArr.push(root.val);
inorderTraversal(root.right);
}
inorderTraversal(root);
return resultArr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//解法2:迭代解法,借用栈来实现
var inorderTraversal = function(root) {
var result = [];
var stack = [];
var cur = root;
while(cur!=null||stack.length!=0){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
result.push(cur.val);
cur = cur.right;
}
return result;
}
分享到