对本场比赛的一些看法
本场比赛二三四题都是很不错的题。
三四题稍微有点难度需要进行一定的思考，所以这篇文章重点来说一下。
今天的每道题都是多解题，本文只提供比赛时的代码和想法，建议大家可以去再多多思考一下。
1856. 一道使用单调栈解决的题目，与LC84相似
1857. 此题考核了两个考点，一是有向图找环，二是拓展排序
1856. Maximum Subarray Min-Product
题意：
给你一个数组，现在对于一个subarray，它的minProduct 是 min(subArray) * sum(subArray)。请找出最大的minProduct 是多少
[2,3,3,1,2] => 3 * (3+3) = 3 * 6 = 18
思路：
- 做这题前强烈建议大家先去看一下LC84，这可以说是一模一样的题目，唯一变了的就是长方形的width变成了每个对应的A[i]而不是1，LC84是一道非常经典的单调栈题目，强烈推荐学习
- 这里我们要保持一个递增的栈，栈里面存两个数，一个是A[i]，一个使cumulative sum
- 如果当前数字比stack的top 要小的话，我们就要把这个stack给pop 掉同时去记录cumulative sum同时update答案，详细的可以看代码和comment的例子演变
代码：
class Solution { public int maxSumMinProduct(int[] A) { long res = 0; Stack < long[] > sta = new Stack < > (); for (int i = 0; i < A.length; i++) { long pair[] = new long[] {A[i], A[i]}; long sum = 0; while (sta.size() > 0 && A[i] <= sta.peek()[0]) { long top[] = sta.pop(); sum += top[1]; res = Math.max(res, sum * top[0]); } pair[1] += sum; sta.push(pair); } long sum = 0; while (sta.size() > 0) { long top[] = sta.pop(); sum += top[1]; res = Math.max(res, top[0] * sum); } return (int)(res % 1000000007); } } //例子：A= [2,3,3,1,2] // 0 : stack [[2,2]] // 1 : stack [[2,2],[3,3]] // 2 : stack [[2,2],[3,6]] => update res=max(res,3*3) // 3 : stack [[1,9]] => update res=max(res,3*6),res=max(res,2*8) // 4 : stack [[1,9] [2,2]] //final update // stack [[1,9]] res=max(res,2*2) // stack [] res=max(res,1*11)
空间复杂度和时间复杂度：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
1857. Largest Color Value in a Directed Graph
题意：
给一个有向图，每个vertex都被标记了一个小字母 (a-z)，对于任意的path，他们都有字母和其对应的频率，我们要找出最大的频率是多少？如果这个图有环的话我们直接输出 -1
思路：
- 首先我们可以做一下有向图找环的算法去查一下这图有没有环，如果有环我们可以直接输出-1，如果没有环那说明这图是acyclic的，那就好办多了
- 现在当前的图是一个无环的有向图。我们可以做一个Topological Sort 一层一层的把它给剥开来，并且我们可以试着枚举以每个点作为path的终点时的可能性
- 我们可以想象一下，如果当前的vertex 是 v 并且它是一个path的终点的话，我们有很多种方法可以到达v，但是无论哪种方法都好，它们都要经过v 的parent才能到达v
- 假设我们都已经记录好了 v 的每个parent作为终点的26字母可达到的最大频率，对于当前v来说，我们只需要选其中最大的那个并传递下来就可以
- 这里我们用一个二维数组 dp[n][26]，dp[v] 代表如果以 v 作为path的 终点 的话，它每个字母可达到的最高频率
- 那么 dp[v][i] = max(dp[v.parents][i])
代码：
class Solution { boolean visit[]; boolean cycle = false; public int largestPathValue(String s, int[][] edges) { int n = s.length(); int in [] = new int[n]; visit = new boolean[n]; List < Integer > g[] = new ArrayList[n]; Arrays.setAll(g, e -> new ArrayList<>()); for (int e[]: edges) { int u = e[0], v = e[1]; g[u].add(v); //建立图，使用adjecent list in [v]++; //记录入度 } for (int i = 0; i < n; i++) { if (!visit[i]) { visit[i] = true; boolean stack[] = new boolean[n]; stack[i] = true; dfs(g, i, stack); //有向图找环 } } if (cycle) return -1; //发现环，直接输出-1 //无环图 int dp[][] = new int[n][26]; Queue < Integer > q = new LinkedList < > (); for (int i = 0; i < n; i++) { if ( in [i] == 0) {//把入度为0的丢进queue里 q.add(i); dp[i][s.charAt(i) - 'a']++; } } //进行topological sort while (q.size() != 0) { int root = q.poll(); for (int next: g[root]) { in [next]--; for (int i = 0; i < 26; i++) {//选所有parent里频率最大的那个 dp[next][i] = Math.max(dp[next][i], dp[root][i]); } if ( in [next] == 0) { //移除掉所有的parent，可以丢进queue里 dp[next][s.charAt(next) - 'a']++; q.add(next); } } } int res = 0; for (int i = 0; i < n; i++) { //更新答案 for (int j = 0; j < dp[0].length; j++) { res = Math.max(res, dp[i][j]); } } return res; } public void dfs(List < Integer > g[], int root, boolean stack[]) { //有向图找环算法 for (int next: g[root]) { if (visit[next]) { if (stack[next]) { cycle = true; } } else { visit[next] = true; stack[next] = true; dfs(g, next, stack); stack[next] = false; } } } }
空间复杂度和时间复杂度：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
好了，以上就是本周周赛的内容，如果喜欢这篇文章，记得给我点赞、在看、留言哦，我们下期见！
