额。。。。昨天在忙作业和实习的事情，题目就没刷了。。。太懒
84. Largest Rectangle in Histogram
如果高度一致都是递增的就一直压入栈，一旦遇到一个高度减小的，就计算栈里面能够组成的最大四边形面积（一个个出栈分别计算四边形面积），不过，我还是不能理解为怎么求最大面积。。。
public class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<Integer>();
int n = heights.length;
int i = 0;
int maxarea = 0;
int temp = 0;
int tempTop = 0;
while (i <= n) {
temp = (i == n?0:heights[i]);
if (stack.isEmpty() || temp > heights[stack.peek()]) {
stack.push(i);
i++;
}
else {
tempTop = heights[stack.pop()];
maxarea = Math.max(maxarea, tempTop * (stack.isEmpty()?i:i – 1 – stack.peek()));
}
}
return maxarea;
}
}
88. Merge Sorted Array
这个简单，从最高位置开始，比较两个array的值，那个大就插入哪个
public class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m – 1;
int j = n – 1;
int index = m + n – 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[index–] = nums1[i–];
}
else {
nums1[index–] = nums2[j–];
}
}
while (i >= 0) {
nums1[index–] = nums1[i–];
}
while (j >= 0) {
nums1[index–] = nums2[j–];
}
}
}
90. Subsets II
也使用递归方法，DFS。
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
Arrays.sort(nums);
List<Integer> subset = new ArrayList<>();
helper(nums, 0, subset, results);
return results;
}
public void helper(int[] nums, int startIndex, List<Integer> subset, List<List<Integer>> results) {
results.add(new ArrayList<Integer>(subset));
for (int i = startIndex; i < nums.length; i++ ) {
if (i!=0 && nums[i]==nums[i-1] && i>startIndex) {
continue;
}
subset.add(nums[i]);
helper(nums, i+1, subset, results);
subset.remove(subset.size() – 1);
}
}
}