题目 n 位格雷码序列 是一个由 2n 个整数组成的序列，其中： 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1） 第一个整数是 0 一个整数在序列中出现 不超过一次 每对 相邻 整数的二进制表示 恰好一位不同 ，且 第一个 和 最后一个 整数的二进制表示 恰好一位不同 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。   示例 1： 输入：n = 2 输出：[0,1,3,2] 解释： [0,1,3,2] 的二进制表示是 [00,01,11,10] 。 - 00 和 01 有一位不同 - 01 和 11 有一位不同 - 11 和 10 有一位不同 - 10 和 00 有一位不同 [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。 - 00 和 10 有一位不同 - 10 和 11 有一位不同 - 11 和 01 有一位不同 - 01 和 00 有一位不同 示例 2： 输入：n = 1 输出：[0,1] ```  提示： 1 <= n <= 16 ###思路 格雷码公式，第i个格雷码为i^(i/2),

题目 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。   示例 1： 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2： 输入：nums = [0] 输出：[[],[0]] 思路 记nums的长度为n。nums每一位数字有在子集与不在子集两种状态，共有2n种组合， 即2n个子集。遍历2n种组合，即可得到所有的子集。用0表示nums[i]不 在子集，1表示nums[i]在子集。则每一种组合都是一个二进制数，并且二进制数的范围为大于等于0， 小于等于2n-1。对于第i位的1来说，可以按位与1<<i得到结果,第i为1，其他都是0都是0 的结果。如果这个结果不为0，则把第i位的数字放入子集。 代码 class Solution { public: vector<vector<int>> subsets(vector<int>& nums) {

题目 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 示例 1： 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6 示例 2： 输入：matrix = [] 输出：0 示例 3： 输入：matrix = [["0"]] 输出：0 示例 4： 输入：matrix = [["1"]] 输出：1 示例 5： 输入：matrix = [["0","0"]] 输出：0 提示： rows == matrix.length cols == matrix[0].length 1 <= row, cols <= 200 matrix[i][j] 为 '0' 或 '1' 思路 本题第一反应就是暴力。枚举每一个矩形，看是否符合要求。但是时间复杂度高达O(rows2cols2), 这么高的复杂度，肯定是过不了所有用例的。上一篇讲了柱状图的题，本题可以转换为柱状图

题目 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。   示例 1: 输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10 示例 2： 输入： heights = [2,4] 输出： 4 提示： 1 <= heights.length <=105 0 <= heights[i] <= 104 思路 遍历数组，以每一个高度向左右两边扩展形成的最大矩形，即是一个候选答案。 从所有候选答案中选择最大值就是答案。对于第i个高度，向左扩展， 找到第一个比i高度小的值，就停止，假设其下标为l。向右扩展，找到第一个比i高度小的值， 就停止,假设其下标为r。那么高度i所能形成的最大矩形面积就是 (r-l-1)*heights[i]。 比较所有的值，就可以找到最大值。怎么找l和r呢?看i-1的高度是否比i高度小，如果小，那就找到了l。 如果不小，则舍弃i-1，看i-2的值，是否比i高度小，如果小，那就找到了l。如果不小，则舍弃i-2,

题目 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 输入：height = [4,2,0,3,2,5] 输出：9 提示： n == height.length 1 <= n <= 2 * 104 0 <= height[i] <= 105 思路 能接雨水，必须是一个凹槽，两端大，中间小。计算每一个凹槽的接雨量，并汇总就是答案。柱子形成一个凹槽必然是先下降，后上升。遍历数组，用一个栈来记录从大到小的高度，大的在栈底，小的在栈顶。如果遇到比栈顶大的，则以当前位置为右侧，栈顶为底部，栈顶第二个元素为左侧形成一个凹槽。计算当前这个凹槽的面积。然后出栈，继续看以当前位置为右侧，栈顶为底部，栈顶第二个元素为左侧，是否能形成一个凹槽，如果能，则继续计算面积。 代码 c