leetcode1124

1. leetcode1124

 给你一份工作时间表   ，上面记录着某一位员工每天的工作小时数。我们认为当员工一天中的工作小时数大于   8   小时的时候，那么这一天就是   劳累的一天 。所谓  表现良好的时间段  ，意味在这段时间内，  劳累的天数  是严格大于  不劳累的天数  。请你返回表现良好时间段的  最大长度  。
   这道题很有意思，首先我们根本就不关心每天具体的工作时间，仅仅关心它是否大于   8  ，所以只需要用两个标志位就可以用来标记表示每一天的工作时间，很容易联想到的就是   0   和   1  。但是对于本题我们需要对两种表示的数量大小关系进行比较，  0   和   1   的表示不能让我们进行直观的比较。考虑换成    -1   和   1  ，这样就可以用元素和来直观地表示元素数量的大小关系了。而元素和的计算很容易想到的办法就是用前缀和，   可以直接由    计算得出。至此，我们的目的就非常清晰了，建立前缀和数组   ，对于所有满足   的   ，找出其中    的最大值。
   首先确定候选的左端点   ，采取从前向后的遍历方式，因为我们要求的是    的最大值，   自然要越小越好。对于   ，如果有   ，那么无论何时我们都可以用    替换   得到更大的结果，所以如果我们已经处理过    ，那么在寻找新的候选左端点    的时候只需要考虑    的情况，因为只有这样    才有可能大于   。构建一个单调递减栈    保存候选左端点的索引，首先将   0   压栈，之后遍历遍历数组，当且仅当当前值小于栈顶对应值的时候将当前索引压栈。而对于右端点   ，采取的是从后向前的遍历方式，首先比较    与    的大小，若    则直接将栈顶弹出，循环操作直到栈为空或者   。这一步可以这么理解，如果前面的候选右端点想要有更大的结果则必须找到更靠前的左端点与之配对。如果栈空，则表示已经没有候选左端点了，直接跳出循环。需要注意的是，循环需要维护    这一条件。

2. Leetcode【526、667、932】

 这道题是一道构造题，即 构造一个长度为 N 的自然序列，满足整除关系：  i % nums[i] = 0  或  nums[i] % i = 0 （i 为第 i 个位置）。 由于看到数据范围 N <= 15，因此很容易想到这道题用深搜（DFS）去做。
   刚开始的做法是先通过 DFS 构造出一个个完整的序列，然后再对完整序列判断每个位置是否满足要求，结果 TLE 了。 后来又想了一下，其实可以在构造的过程中就判断当前构造的这个序列的每个位置是否满足上述整除关系，如果有一个位置不满足，就不用继续构造下去了（即相当于剪枝操作）。 这样省了一大笔时间，题目就 AC 了。
   这道题是一道构造题，即 构造一个长度为 n 的自然序列，这个序列相邻元素差的绝对值的数量为 k 个。 看到数据范围是 10^4，首先排除用 DFS 的方法构造序列，然后判断是否满足题意的这种做法。
   但是，乍一看也没有什么思路。因此需要从数学的角度找找规律。 首先可以确定一点：对于长度为 n 的序列，元素差最多为 n-1 个，且这 n-1 个差分别为 1~(n-1)。这 n-1 个差的构成也很容易发现，较小的数和较大的数交替形成的序列就满足要求。 
   举个例子，假设 n = 8，k = 7，那么这个序列就是 1 8 2 7 3 6 4 5，形成的 k 个元素差为：7 6 5 4 3 2 1；若 k 不等于 n-1，假设 k = 4，我们只需要按上述规律形成满足长度为 k+1 的序列，剩余元素按递增顺序安排即可（剩余数的差值都为 1），最终得到的序列是：(1 5 2 4 3) 6 7 8，形成的 k 个元素差为：(4 3 2 1) 3 1 1（后面 3 个数的差值为 1）。
    时间复杂度为 O(n)。 
   这道题也是一道构造题，即 构造一个长度为 N 的自然序列，这个序列满足条件： 对于任意的  i < j < k ，有  2 * A[k] != A[i] + A[j] 。这个序列叫做美丽数组 看到数据范围是 1000，首先也先排除用 DFS 的方法构造序列，然后判断是否满足题意的这种做法。
   但是，乍一看也没有什么思路。因此需要从数学的角度找找规律。注意到，美丽数组有如下数学性质：   1、A 是一个漂亮数组，对于 A 中的位置 k，k 左边的都是奇数，k 右边的都是偶数（或者 k 左边的都是偶数，k 右边的都是奇数），因为这样安排就一定能保证  2 * A[k] != A[i] + A[j]  （偶数 != 奇数 + 偶数 或 偶数 != 偶数 + 奇数）;   2、A 是一个漂亮数组，如果对 A 中所有元素加（或减）一个常数，那么 A 还是一个漂亮数组；   3、A 是一个漂亮数组，如果对 A 中所有元素乘上一个常数，那么 A 还是一个漂亮数组；   4、A 是一个漂亮数组，如果删除A 中的一些元素，那么 A 还是一个漂亮数组，因为是对于任意的  i < k < j  都有  2 * A[k] != A[i] + A[j] ，删除一些元素并不会改变这种顺序；    5、A 是一个由奇数构成的漂亮数组，B 是一个偶数构成的漂亮数组，那么 A + B 也是一个漂亮数组，如:  {1,5,3,7} + {2,6,4,8} = {1,5,3,7,2,6,4,8}  也是一个漂亮数组。 
   有了上述几条性质，我们就可以解决本题的构造问题了。
    我们知道一个漂亮数组 A 可以分为奇数部分 A1 和偶数部分 A2（性质 1）。此时如果有一个漂亮数组 B，那么  2*B-1  是一个漂亮数组（性质 2、3）并且是奇数数组，而  2*B  也是一个漂亮数组（性质 2）并且是偶数数组。那么我们通过 [2*B-1] + [2*B]  得到的必然也是一个漂亮数组（性质 5）。 
   所以我们 从最简单的 ans = [1] 开始推导，构造奇数  [(2*i-1) for i in ans]  + 偶数  [2*i for i in ans] 拼接在一起成为新的美丽数组； 如果当前构造的美丽数组的长度小于 N，就继续这个操作，就能使得得到的一直是美丽数组。 因为每次构造的美丽数组的长度是 2 的整数次方，所以最后要把结果中小于等于 N 的留下来，大于 N 的数字删除即可（性质 4）。 
   因为构造的美丽数组的长度是随着 2 的整数次方增长的，因此外层循环是 O(logN) 级别，内层循环是 O(N) 级别，总时间复杂度为 O(N*logN)；空间复杂度为 O(N)。